{"id":8219,"date":"2021-03-06T23:30:38","date_gmt":"2021-03-07T07:30:38","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8219"},"modified":"2021-03-07T10:37:08","modified_gmt":"2021-03-07T18:37:08","slug":"leetcode-1786-number-of-restricted-paths-from-first-to-last-node","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1786-number-of-restricted-paths-from-first-to-last-node\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1786. Number of Restricted Paths From First to Last Node"},"content":{"rendered":"\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1786. Number of Restricted Paths From First to Last Node - \u5237\u9898\u627e\u5de5\u4f5c EP388\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/1VN6h1sohAs?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>\n<\/div><\/figure>\n\n\n\n<p>There is an undirected weighted connected graph. You are given a positive integer&nbsp;<code>n<\/code>&nbsp;which denotes that the graph has&nbsp;<code>n<\/code>&nbsp;nodes labeled from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>, and an array&nbsp;<code>edges<\/code>&nbsp;where each&nbsp;<code>edges[i] = [u<sub>i<\/sub>, v<sub>i<\/sub>, weight<sub>i<\/sub>]<\/code>&nbsp;denotes that there is an edge between nodes&nbsp;<code>u<sub>i<\/sub><\/code>&nbsp;and&nbsp;<code>v<sub>i<\/sub><\/code>&nbsp;with weight equal to&nbsp;<code>weight<sub>i<\/sub><\/code>.<\/p>\n\n\n\n<p>A path from node&nbsp;<code>start<\/code>&nbsp;to node&nbsp;<code>end<\/code>&nbsp;is a sequence of nodes&nbsp;<code>[z<sub>0<\/sub>, z<sub>1<\/sub>,z<sub>2<\/sub>, ..., z<sub>k<\/sub>]<\/code>&nbsp;such that&nbsp;<code>z<sub>0&nbsp;<\/sub>= start<\/code>&nbsp;and&nbsp;<code>z<sub>k<\/sub>&nbsp;= end<\/code>&nbsp;and there is an edge between&nbsp;<code>z<sub>i<\/sub><\/code>&nbsp;and&nbsp;<code>z<sub>i+1<\/sub><\/code>&nbsp;where&nbsp;<code>0 &lt;= i &lt;= k-1<\/code>.<\/p>\n\n\n\n<p>The distance of a path is the sum of the weights on the edges of the path. Let&nbsp;<code>distanceToLastNode(x)<\/code>&nbsp;denote the shortest distance of a path between node&nbsp;<code>n<\/code>&nbsp;and node&nbsp;<code>x<\/code>. A&nbsp;<strong>restricted path<\/strong>&nbsp;is a path that also satisfies that&nbsp;<code>distanceToLastNode(z<sub>i<\/sub>) &gt; distanceToLastNode(z<sub>i+1<\/sub>)<\/code>&nbsp;where&nbsp;<code>0 &lt;= i &lt;= k-1<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the number of restricted paths from node<\/em>&nbsp;<code>1<\/code>&nbsp;<em>to node<\/em>&nbsp;<code>n<\/code>. Since that number may be too large, return it&nbsp;<strong>modulo<\/strong>&nbsp;<code>10<sup>9<\/sup>&nbsp;+ 7<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/02\/17\/restricted_paths_ex1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> Each circle contains the node number in black and its <code>distanceToLastNode value in blue. <\/code>The three restricted paths are:\n1) 1 --&gt; 2 --&gt; 5\n2) 1 --&gt; 2 --&gt; 3 --&gt; 5\n3) 1 --&gt; 3 --&gt; 5\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/02\/17\/restricted_paths_ex22.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> Each circle contains the node number in black and its <code>distanceToLastNode value in blue. <\/code>The only restricted path is 1 --&gt; 3 --&gt; 7.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 2 * 10<sup>4<\/sup><\/code><\/li><li><code>n - 1 &lt;= edges.length &lt;= 4 * 10<sup>4<\/sup><\/code><\/li><li><code>edges[i].length == 3<\/code><\/li><li><code>1 &lt;= u<sub>i<\/sub>, v<sub>i<\/sub>&nbsp;&lt;= n<\/code><\/li><li><code>u<sub>i&nbsp;<\/sub>!= v<sub>i<\/sub><\/code><\/li><li><code>1 &lt;= weight<sub>i<\/sub>&nbsp;&lt;= 10<sup>5<\/sup><\/code><\/li><li>There is at most one edge between any two nodes.<\/li><li>There is at least one path between any two nodes.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Dijkstra + DFS w\/ memoization<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-1.png\" alt=\"\" class=\"wp-image-8225\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<p>Find shortest path from n to all the nodes.<br>paths(u) = sum(paths(v)) if dist[u] &gt; dist[v] and (u, v) has an edge<br>return paths(1)<\/p>\n\n\n\n<p>Time complexity: O(ElogV + V + E)<br>Space complexity: O(V + E)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n    constexpr int kMod = 1e9 + 7;\n    using PII = pair<int, int>;    \n    vector<vector<PII>> g(n + 1);\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    \n    \/\/ Shortest distance from n to x.\n    vector<int> dist(n + 1, INT_MAX \/ 2);\n    dist[n] = 0;\n    priority_queue<PII, vector<PII>, std::greater<PII>> q;\n    q.emplace(0, n);\n    while (!q.empty()) {\n      const auto [d, u] = q.top(); q.pop();\n      if (dist[u] < d) continue;\n      for (auto [v, w]: g[u]) {\n        if (dist[u] + w >= dist[v]) continue;\n        dist[v] = dist[u] + w;\n        q.emplace(dist[v], v);\n      }\n    }\n\n    vector<int> dp(n + 1, INT_MAX);\n    function<int(int)> dfs = [&](int u) {      \n      if (u == n) return 1;\n      if (dp[u] != INT_MAX) return dp[u];\n      int ans = 0;\n      for (auto [v, w]: g[u])\n        if (dist[u] > dist[v])\n          ans = (ans + dfs(v)) % kMod;      \n      return dp[u] = ans;\n    };\n    \n    return dfs(1);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>Combined<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-2.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-2.png\" alt=\"\" class=\"wp-image-8226\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><a href=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-3.png\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-3.png\" alt=\"\" class=\"wp-image-8227\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2021\/03\/1786-ep388-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/figure>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n    constexpr int kMod = 1e9 + 7;\n    using PII = pair<int, int>;    \n    vector<vector<PII>> g(n + 1);\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    \n    \/\/ Shortest distance from n to x.\n    vector<int> dist(n + 1, INT_MAX);\n    vector<int> dp(n + 1);\n    dist[n] = 0;\n    dp[n] = 1;\n    priority_queue<PII, vector<PII>, std::greater<PII>> q;\n    q.emplace(0, n);\n    while (!q.empty()) {\n      const auto [d, u] = q.top(); q.pop();\n      if (d > dist[u]) continue;\n      if (u == 1) break;\n      for (auto [v, w]: g[u]) {\n        if (dist[v] > dist[u] + w)\n          q.emplace(dist[v] = dist[u] + w, v);\n        if (dist[v] > dist[u])\n          dp[v] = (dp[v] + dp[u]) % kMod;\n      }\n    }    \n    return dp[1];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>There is an undirected weighted connected graph. You are given a positive integer&nbsp;n&nbsp;which denotes that the graph has&nbsp;n&nbsp;nodes labeled from&nbsp;1&nbsp;to&nbsp;n, and an array&nbsp;edges&nbsp;where each&nbsp;edges[i] =&#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":[540,18,77,177,87],"class_list":["post-8219","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dijkstra","tag-dp","tag-graph","tag-medium","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8219","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=8219"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8219\/revisions"}],"predecessor-version":[{"id":8229,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8219\/revisions\/8229"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8219"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8219"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8219"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}