{"id":8685,"date":"2021-11-07T14:09:43","date_gmt":"2021-11-07T22:09:43","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8685"},"modified":"2021-11-07T14:10:45","modified_gmt":"2021-11-07T22:10:45","slug":"leetcode-2065-maximum-path-quality-of-a-graph","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-2065-maximum-path-quality-of-a-graph\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2065. Maximum Path Quality of a Graph"},"content":{"rendered":"\n

There is an undirected<\/strong> graph with n<\/code> nodes numbered from 0<\/code> to n - 1<\/code> (inclusive<\/strong>). You are given a 0-indexed<\/strong> integer array values<\/code> where values[i]<\/code> is the value <\/strong>of the ith<\/sup><\/code> node. You are also given a 0-indexed<\/strong> 2D integer array edges<\/code>, where each edges[j] = [uj<\/sub>, vj<\/sub>, timej<\/sub>]<\/code> indicates that there is an undirected edge between the nodes uj<\/sub><\/code> and vj<\/sub><\/code>,and it takes timej<\/sub><\/code> seconds to travel between the two nodes. Finally, you are given an integer maxTime<\/code>.<\/p>\n\n\n\n

A valid<\/strong> path<\/strong> in the graph is any path that starts at node 0<\/code>, ends at node 0<\/code>, and takes at most<\/strong> maxTime<\/code> seconds to complete. You may visit the same node multiple times. The quality<\/strong> of a valid path is the sum<\/strong> of the values of the unique nodes<\/strong> visited in the path (each node’s value is added at most once<\/strong> to the sum).<\/p>\n\n\n\n

Return the maximum<\/strong> quality of a valid path<\/em>.<\/p>\n\n\n\n

Note:<\/strong> There are at most four<\/strong> edges connected to each node.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49\nOutput:<\/strong> 75\nExplanation:<\/strong>\nOne possible path is 0 -> 1 -> 0 -> 3 -> 0. The total time taken is 10 + 10 + 10 + 10 = 40 <= 49.\nThe nodes visited are 0, 1, and 3, giving a maximal path quality of 0 + 32 + 43 = 75.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30\nOutput:<\/strong> 25\nExplanation:<\/strong>\nOne possible path is 0 -> 3 -> 0. The total time taken is 10 + 10 = 20 <= 30.\nThe nodes visited are 0 and 3, giving a maximal path quality of 5 + 20 = 25.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50\nOutput:<\/strong> 7\nExplanation:<\/strong>\nOne possible path is 0 -> 1 -> 3 -> 1 -> 0. The total time taken is 10 + 13 + 13 + 10 = 46 <= 50.\nThe nodes visited are 0, 1, and 3, giving a maximal path quality of 1 + 2 + 4 = 7.<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> values = [0,1,2], edges = [[1,2,10]], maxTime = 10\nOutput:<\/strong> 0\nExplanation:<\/strong> \nThe only path is 0. The total time taken is 0.\nThe only node visited is 0, giving a maximal path quality of 0.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == values.length<\/code><\/li>
  • 1 <= n <= 1000<\/code><\/li>
  • 0 <= values[i] <= 108<\/sup><\/code><\/li>
  • 0 <= edges.length <= 2000<\/code><\/li>
  • edges[j].length == 3<\/code><\/li>
  • 0 <= uj <\/sub>< vj<\/sub> <= n - 1<\/code><\/li>
  • 10 <= timej<\/sub>, maxTime <= 100<\/code><\/li>
  • All the pairs [uj<\/sub>, vj<\/sub>]<\/code> are unique<\/strong>.<\/li>
  • There are at most four<\/strong> edges connected to each node.<\/li>
  • The graph may not be connected.<\/li><\/ul>\n\n\n\n
    Solution: DFS<\/strong><\/h2>\n\n\n\n
    Given time >= 10 and maxTime <= 100, the path length is at most 10, given at most four edges connected to each node.
    Time complexity: O(410<\/sup>)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maximalPathQuality(vector& values, vector>& edges, int maxTime) {\n    const int n = values.size();\n    vector>> g(n);\n    for (const auto& e : edges) {\n      g[e[0]].emplace_back(e[1], e[2]);\n      g[e[1]].emplace_back(e[0], e[2]);\n    }\n    vector seen(n);\n    int ans = 0;\n    function dfs = [&](int u, int t, int s) {\n      if (++seen[u] == 1) s += values[u];\n      if (u == 0) ans = max(ans, s);\n      for (auto [v, d] : g[u])\n        if (t + d <= maxTime) dfs(v, t + d, s);\n      if (--seen[u] == 0) s -= values[u];\n    };\n    dfs(0, 0, 0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    There is an undirected graph with n nodes numbered from 0 to n – 1 (inclusive). You are given a 0-indexed integer array values where values[i] is the value of the ith node. You are also given a 0-indexed 2D integer array edges, where each edges[j] =…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[33,217,42],"class_list":["post-8685","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-hard","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8685","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8685"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8685\/revisions"}],"predecessor-version":[{"id":8688,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8685\/revisions\/8688"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8685"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8685"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8685"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}