{"id":3439,"date":"2018-08-04T20:49:13","date_gmt":"2018-08-05T03:49:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3439"},"modified":"2018-08-18T10:17:48","modified_gmt":"2018-08-18T17:17:48","slug":"leetcode-882-reachable-nodes-in-subdivided-graph","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-882-reachable-nodes-in-subdivided-graph\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 882. Reachable Nodes In Subdivided Graph"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 882. Reachable Nodes In Subdivided Graph - \u5237\u9898\u627e\u5de5\u4f5c EP215\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/SGki2XeWBEo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>Starting with an\u00a0<strong>undirected<\/strong>\u00a0graph (the &#8220;original graph&#8221;) with nodes from\u00a0<code>0<\/code>\u00a0to\u00a0<code>N-1<\/code>, subdivisions are made to some of the edges.<\/p>\n<p>The graph is given as follows:\u00a0<code>edges[k]<\/code>\u00a0is a list of integer pairs\u00a0<code>(i, j, n)<\/code>\u00a0such that\u00a0<code>(i, j)<\/code>\u00a0is an edge of the original graph,<\/p>\n<p>and\u00a0<code>n<\/code>\u00a0is the total number of\u00a0<strong>new<\/strong>\u00a0nodes on that edge.<\/p>\n<p>Then, the edge\u00a0<code>(i, j)<\/code>\u00a0is deleted from the original graph,\u00a0<code>n<\/code>\u00a0new nodes\u00a0<code>(x_1, x_2, ..., x_n)<\/code>\u00a0are added to the original graph,<\/p>\n<p>and\u00a0<code>n+1<\/code>\u00a0new\u00a0edges\u00a0<code>(i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j)<\/code>\u00a0are added to the original\u00a0graph.<\/p>\n<p>Now, you start at node\u00a0<code>0<\/code>\u00a0from the original graph, and in each move, you travel along one\u00a0edge.<\/p>\n<p>Return how many nodes you can reach in at most\u00a0<code>M<\/code>\u00a0moves.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false \"><strong>Input: <\/strong>edge = <span id=\"example-input-1-1\">[[0,1,10],[0,2,1],[1,2,2]]<\/span>, M = <span id=\"example-input-1-2\">6<\/span>, N = <span id=\"example-input-1-3\">3<\/span> \r\n<strong>Output: <\/strong><span id=\"example-output-1\">13<\/span> \r\n<strong>Explanation: <\/strong> The nodes that are reachable in the final graph after M = 6 moves are indicated below. <img decoding=\"async\" src=\"https:\/\/s3-lc-upload.s3.amazonaws.com\/uploads\/2018\/08\/01\/origfinal.png\" alt=\"\" \/><\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4 \r\n<strong>Output: <\/strong>23<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>0 &lt;= edges.length &lt;= 10000<\/code><\/li>\n<li><code>0 &lt;= edges[i][0] &lt;\u00a0edges[i][1] &lt; N<\/code><\/li>\n<li>There does not exist any\u00a0<code>i != j<\/code>\u00a0for which\u00a0<code>edges[i][0] == edges[j][0]<\/code>\u00a0and\u00a0<code>edges[i][1] == edges[j][1]<\/code>.<\/li>\n<li>The original graph\u00a0has no parallel edges.<\/li>\n<li><code>0 &lt;= edges[i][2] &lt;= 10000<\/code><\/li>\n<li><code>0 &lt;= M &lt;= 10^9<\/code><\/li>\n<li><code><span style=\"font-family: monospace;\">1 &lt;= N &lt;= 3000<\/span><\/code><\/li>\n<\/ol>\n<h1><strong>Solution: Dijkstra Shortest Path<\/strong><\/h1>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3468\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3467\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-3472\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/08\/866-ep215-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p>Compute the shortest from 0 to rest of the nodes. Use HP to mark the maximum moves left to reach each node.<\/p>\n<p>HP[u] = a, HP[v] = b, new_nodes[u][v] = c<\/p>\n<p>nodes covered between a&lt;-&gt;b = min(c, a + b)<\/p>\n<p>Time complexity: O(ElogE)<\/p>\n<p>Space complexity: O(E)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 88 ms\r\nclass Solution {\r\npublic:\r\n  int reachableNodes(vector&lt;vector&lt;int&gt;&gt;&amp; edges, int M, int N) {\r\n    unordered_map&lt;int, unordered_map&lt;int, int&gt;&gt; g;\r\n    for (const auto&amp; e : edges)\r\n      g[e[0]][e[1]] = g[e[1]][e[0]] = e[2];\r\n    \r\n    priority_queue&lt;pair&lt;int, int&gt;&gt; q;   \/\/ {hp, node}, sort by HP desc\r\n    unordered_map&lt;int, int&gt; HP;         \/\/ node -&gt; max HP left\r\n    q.push({M, 0});\r\n    while (!q.empty()) {\r\n      int hp = q.top().first;\r\n      int cur = q.top().second;\r\n      q.pop();\r\n      if (HP.count(cur)) continue;\r\n      HP[cur] = hp;\r\n      for (const auto&amp; pair : g[cur]) {\r\n        int nxt = pair.first;\r\n        int nxt_hp = hp - pair.second - 1;\r\n        if (HP.count(nxt) || nxt_hp &lt; 0) continue;\r\n        q.push({nxt_hp, nxt});\r\n      }\r\n    }\r\n    \r\n    int ans = HP.size(); \/\/ Original nodes covered.\r\n    for (const auto&amp; e : edges) {\r\n      int uv = HP.count(e[0]) ? HP[e[0]] : 0;\r\n      int vu = HP.count(e[1]) ? HP[e[1]] : 0;\r\n      ans += min(e[2], uv + vu);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>Optimized Dijkstra (replace hashmap with vector)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 56 ms (beats 88%)\r\nclass Solution {\r\npublic:\r\n  int reachableNodes(vector&lt;vector&lt;int&gt;&gt;&amp; edges, int M, int N) {\r\n    vector&lt;vector&lt;pair&lt;int, int&gt;&gt;&gt; g(N);\r\n    for (const auto&amp; e : edges) {\r\n      g[e[0]].emplace_back(e[1], e[2]);\r\n      g[e[1]].emplace_back(e[0], e[2]);\r\n    }\r\n    \r\n    set&lt;pair&lt;int, int&gt;&gt; q;           \/\/ {hp, node}, sort by HP asc\r\n    vector&lt;int&gt; HP(N, INT_MIN);      \/\/ node -&gt; HP left\r\n    q.insert({M, 0});\r\n    int ans = 0;\r\n    while (!q.empty()) {\r\n      auto last_it = prev(end(q));\r\n      int hp = last_it-&gt;first;\r\n      int cur = last_it-&gt;second;\r\n      q.erase(last_it);\r\n      if (HP[cur] != INT_MIN) continue;\r\n      HP[cur] = hp;\r\n      ++ans;\r\n      for (const auto&amp; pair : g[cur]) {\r\n        int nxt = pair.first;\r\n        int nxt_hp = hp - pair.second - 1;\r\n        if (nxt_hp &lt; 0 || HP[nxt] != INT_MIN) continue;\r\n        q.insert({nxt_hp, nxt});\r\n      }\r\n    }\r\n        \r\n    for (const auto&amp; e : edges) {\r\n      const int uv = HP[e[0]] == INT_MIN ?  0 : HP[e[0]];\r\n      const int vu = HP[e[1]] == INT_MIN ?  0 : HP[e[1]];\r\n      ans += min(e[2], uv + vu);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>Using SPFA<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 56 ms (beats 88%)\r\nclass Solution {\r\npublic:\r\n  int reachableNodes(vector&lt;vector&lt;int&gt;&gt;&amp; edges, int M, int N) {\r\n    vector&lt;vector&lt;pair&lt;int, int&gt;&gt;&gt; g(N);\r\n    for (const auto&amp; e : edges) {\r\n      g[e[0]].emplace_back(e[1], e[2]);\r\n      g[e[1]].emplace_back(e[0], e[2]);\r\n    }\r\n    \r\n    queue&lt;int&gt; q;               \r\n    vector&lt;int&gt; HP(N, INT_MIN);\r\n    vector&lt;bool&gt; in_q(N);\r\n    HP[0] = M;\r\n    q.push(0);\r\n    in_q[0] = true;\r\n    \r\n    \/\/ SPFA (Shortest Path Faster Algorithm).\r\n    while (!q.empty()) {      \r\n      int u = q.front(); q.pop();\r\n      in_q[u] = false;\r\n      for (const auto&amp; pair : g[u]) {\r\n        int v = pair.first;\r\n        int new_hp = HP[u] - pair.second - 1;        \r\n        if (new_hp &lt; 0 || new_hp &lt;= HP[v]) continue;\r\n        HP[v] = new_hp;\r\n        if (in_q[v]) continue;\r\n        q.push(v);\r\n        in_q[v] = true;\r\n      }\r\n    }\r\n    \r\n    int ans = 0;\r\n    for (int i = 0; i &lt; N; ++i) ans += HP[i] &gt;= 0;\r\n    for (const auto&amp; e : edges) {\r\n      const int uv = HP[e[0]] == INT_MIN ?  0 : HP[e[0]];\r\n      const int vu = HP[e[1]] == INT_MIN ?  0 : HP[e[1]];\r\n      ans += min(e[2], uv + vu);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>BFS<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 108 ms\r\nclass Solution {\r\npublic:\r\n  int reachableNodes(vector&lt;vector&lt;int&gt;&gt;&amp; edges, int M, int N) {\r\n    unordered_map&lt;int, unordered_map&lt;int, int&gt;&gt; g;\r\n    for (const auto&amp; e : edges)\r\n      g[e[0]][e[1]] = g[e[1]][e[0]] = e[2];\r\n    \r\n    queue&lt;pair&lt;int, int&gt;&gt; q;            \/\/ {hp, node}\r\n    unordered_map&lt;int, int&gt; HP;         \/\/ node -&gt; max HP left\r\n    q.push({M, 0});\r\n    while (!q.empty()) {\r\n      int hp = q.front().first;\r\n      int cur = q.front().second;\r\n      q.pop();\r\n      if (HP.count(cur) &amp;&amp; HP[cur] &gt; hp) continue;\r\n      HP[cur] = hp;\r\n      for (const auto&amp; pair : g[cur]) {\r\n        int nxt = pair.first;\r\n        int nxt_hp = hp - pair.second - 1;\r\n        if (nxt_hp &lt; 0 || (HP.count(nxt) &amp;&amp; HP[nxt] &gt; nxt_hp)) continue;\r\n        q.push({nxt_hp, nxt});\r\n      }\r\n    }\r\n    \r\n    int ans = HP.size(); \/\/ Original nodes covered.\r\n    for (const auto&amp; e : edges) {\r\n      int uv = HP.count(e[0]) ? HP[e[0]] : 0;\r\n      int vu = HP.count(e[1]) ? HP[e[1]] : 0;\r\n      ans += min(e[2], uv + vu);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Starting with an\u00a0undirected\u00a0graph (the &#8220;original graph&#8221;) with nodes from\u00a00\u00a0to\u00a0N-1, subdivisions are made to some of the edges. The graph is given as follows:\u00a0edges[k]\u00a0is a&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[34,77,217,87],"class_list":["post-3439","post","type-post","status-publish","format-standard","hentry","category-graph","tag-bfs","tag-graph","tag-hard","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3439","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=3439"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3439\/revisions"}],"predecessor-version":[{"id":3608,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3439\/revisions\/3608"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3439"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3439"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3439"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}