{"id":1204,"date":"2017-12-12T17:20:09","date_gmt":"2017-12-13T01:20:09","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1204"},"modified":"2017-12-13T08:47:58","modified_gmt":"2017-12-13T16:47:58","slug":"leetcode-743-network-delay-time","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-743-network-delay-time\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 743. Network Delay Time"},"content":{"rendered":"<div class=\"question-description\">\n<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 743. Network Delay Time - \u5237\u9898\u627e\u5de5\u4f5c EP130\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/vwLYDeghs_c?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<p>There are\u00a0<code>N<\/code>\u00a0network nodes, labelled\u00a0<code>1<\/code>\u00a0to\u00a0<code>N<\/code>.<\/p>\n<p>Given\u00a0<code>times<\/code>, a list of travel times as\u00a0<b>directed<\/b>\u00a0edges\u00a0<code>times[i] = (u, v, w)<\/code>, where\u00a0<code>u<\/code>\u00a0is the source node,\u00a0<code>v<\/code>\u00a0is the target node, and\u00a0<code>w<\/code>\u00a0is the time it takes for a signal to travel from source to target.<\/p>\n<p>Now, we send a signal from a certain node\u00a0<code>K<\/code>. How long will it take for all nodes to receive the signal? If it is impossible, return\u00a0<code>-1<\/code>.<\/p>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li><code>N<\/code>\u00a0will be in the range\u00a0<code>[1, 100]<\/code>.<\/li>\n<li><code>K<\/code>\u00a0will be in the range\u00a0<code>[1, N]<\/code>.<\/li>\n<li>The length of\u00a0<code>times<\/code>\u00a0will be in the range\u00a0<code>[1, 6000]<\/code>.<\/li>\n<li>All edges\u00a0<code>times[i] = (u, v, w)<\/code>\u00a0will have\u00a0<code>1 &lt;= u, v &lt;= N<\/code>\u00a0and\u00a0<code>1 &lt;= w &lt;= 100<\/code>.<\/li>\n<\/ol>\n<p><strong>Idea:<\/strong><\/p>\n<p>Construct the graph and do a shortest path from K to all other nodes.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-1213 size-full\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/743-ep130.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/743-ep130.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/743-ep130-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/12\/743-ep130-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><strong>Solution 2:<\/strong><\/p>\n<p>C++ \/ Bellman-Ford<\/p>\n<p>Time complexity: O(ne)<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 92 ms\r\nclass Solution {\r\npublic:\r\n    int networkDelayTime(vector&lt;vector&lt;int&gt;&gt;&amp; times, int N, int K) {\r\n        constexpr int MAX_TIME = 101 * 100;\r\n        vector&lt;int&gt; dist(N, MAX_TIME);\r\n        dist[K - 1] = 0;\r\n        for (int i = 1; i &lt; N; ++i)\r\n            for (const auto&amp; time : times) {\r\n                int u = time[0] - 1, v = time[1] - 1, w = time[2];\r\n                dist[v] = min(dist[v], dist[u] + w);\r\n            }\r\n        int max_dist = *max_element(dist.begin(), dist.end());\r\n        return max_dist == MAX_TIME ? -1 : max_dist;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n<div><\/div>\n<p><strong>Solution3:<\/strong><\/p>\n<p>C++ \/ Floyd-Warshall<\/p>\n<p>Time complexity: O(n^3)<\/p>\n<p>Space complexity: O(n^2)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 92 ms\r\nclass Solution {\r\npublic:\r\n    int networkDelayTime(vector&lt;vector&lt;int&gt;&gt;&amp; times, int N, int K) {\r\n        vector&lt;vector&lt;int&gt;&gt; d(N, vector&lt;int&gt;(N, -1));\r\n        \r\n        for (auto time : times)   \r\n            d[time[0] - 1][time[1] - 1] = time[2];\r\n        \r\n        for (int i = 0; i &lt; N; ++i)\r\n            d[i][i] = 0;\r\n        \r\n        for (int k = 0; k &lt; N; ++k)\r\n            for (int i = 0; i &lt; N; ++i)\r\n                for (int j = 0; j &lt; N; ++j)\r\n                    if (d[i][k] &gt;= 0 &amp;&amp; d[k][j] &gt;= 0)\r\n                        if (d[i][j] &lt; 0 || d[i][j] &gt; d[i][k] + d[k][j])\r\n                            d[i][j] = d[i][k] + d[k][j];\r\n        \r\n        int ans = INT_MIN;        \r\n        \r\n        for (int i = 0; i &lt; N; ++i) {\r\n            if (d[K - 1][i] &lt; 0) return -1;\r\n            ans = max(ans, d[K - 1][i]);\r\n        }\r\n        \r\n        return ans;\r\n    }\r\n};<\/pre>\n<p>v2<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 89 ms\r\nclass Solution {\r\npublic:\r\n    int networkDelayTime(vector&lt;vector&lt;int&gt;&gt;&amp; times, int N, int K) {\r\n        constexpr int MAX_TIME = 101 * 100;\r\n        vector&lt;vector&lt;int&gt;&gt; d(N, vector&lt;int&gt;(N, MAX_TIME));\r\n        \r\n        for (auto time : times)   \r\n            d[time[0] - 1][time[1] - 1] = time[2];\r\n        \r\n        for (int i = 0; i &lt; N; ++i)\r\n            d[i][i] = 0;\r\n        \r\n        for (int k = 0; k &lt; N; ++k)\r\n            for (int i = 0; i &lt; N; ++i)\r\n                for (int j = 0; j &lt; N; ++j)                    \r\n                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);\r\n        \r\n        int max_time = *max_element(d[K - 1].begin(), d[K - 1].end());        \r\n        return max_time &gt;= MAX_TIME ? - 1 : max_time;\r\n    }\r\n};<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>There are\u00a0N\u00a0network nodes, labelled\u00a01\u00a0to\u00a0N. Given\u00a0times, a list of travel times as\u00a0directed\u00a0edges\u00a0times[i] = (u, v, w), where\u00a0u\u00a0is the source node,\u00a0v\u00a0is the target node, and\u00a0w\u00a0is the time&#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,164],"tags":[77,87],"class_list":["post-1204","post","type-post","status-publish","format-standard","hentry","category-graph","category-medium","tag-graph","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1204","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=1204"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1204\/revisions"}],"predecessor-version":[{"id":1225,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1204\/revisions\/1225"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1204"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1204"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}