{"id":1842,"date":"2018-02-22T08:45:40","date_gmt":"2018-02-22T16:45:40","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1842"},"modified":"2018-08-31T12:41:26","modified_gmt":"2018-08-31T19:41:26","slug":"leetcode-787-cheapest-flights-within-k-stops","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-787-cheapest-flights-within-k-stops\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 787. Cheapest Flights Within K Stops"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 787. Cheapest Flights Within K Stops  - \u5237\u9898\u627e\u5de5\u4f5c EP170\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/PLY-lbcxEjg?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>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u57ce\u5e02\u4e4b\u95f4\u7684\u673a\u7968\u4ef7\u683c\uff0c\u95ee\u4ecesrc\u5230dst\u7684\u6700\u5c11\u9700\u8981\u82b1\u591a\u5c11\u94b1\uff0c\u6700\u591a\u53ef\u4ee5\u4e2d\u8f6ck\u4e2a\u673a\u573a\u3002<\/p>\n<p>There are\u00a0<code>n<\/code>\u00a0cities connected by\u00a0<code>m<\/code>\u00a0flights. Each fight starts from city\u00a0<code>u\u00a0<\/code>and arrives at\u00a0<code>v<\/code>\u00a0with a price\u00a0<code>w<\/code>.<\/p>\n<p>Now given all the cities and fights, together with starting city\u00a0<code>src<\/code>\u00a0and the destination\u00a0<code>dst<\/code>, your task is to find the cheapest price from\u00a0<code>src<\/code>\u00a0to\u00a0<code>dst<\/code>\u00a0with up to\u00a0<code>k<\/code>\u00a0stops. If there is no such route, output\u00a0<code>-1<\/code>.<\/p>\n<pre class=\"\">Example 1:\r\nInput: \r\nn = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]\r\nsrc = 0, dst = 2, k = 1\r\nOutput: 200\r\nExplanation: \r\nThe graph looks like this:\r\n\r\nThe cheapest price from city <code>0<\/code> to city <code>2<\/code> with at most 1 stop costs 200, as marked red in the picture.<\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/s3-lc-upload.s3.amazonaws.com\/uploads\/2018\/02\/16\/995.png\" alt=\"\" width=\"200\" \/><\/p>\n<pre class=\"\">Example 2:\r\nInput: \r\nn = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]\r\nsrc = 0, dst = 2, k = 0\r\nOutput: 500\r\nExplanation: \r\nThe graph looks like this:\r\nThe cheapest price from city <code>0<\/code> to city <code>2<\/code> with at most 0 stop costs 500, as marked blue in the picture.<\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/s3-lc-upload.s3.amazonaws.com\/uploads\/2018\/02\/16\/995.png\" alt=\"\" width=\"200\" \/><\/p>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li>The number of\u00a0nodes\u00a0<code>n<\/code>\u00a0will be\u00a0in range\u00a0<code>[1, 100]<\/code>, with nodes labeled from\u00a0<code>0<\/code>\u00a0to\u00a0<code>n<\/code><code>\u00a0- 1<\/code>.<\/li>\n<li>The\u00a0size of\u00a0<code>flights<\/code>\u00a0will be\u00a0in range\u00a0<code>[0, n * (n - 1) \/ 2]<\/code>.<\/li>\n<li>The format of each flight will be\u00a0<code>(src,\u00a0<\/code><code>dst<\/code><code>, price)<\/code>.<\/li>\n<li>The price of each flight will be in the range\u00a0<code>[1, 10000]<\/code>.<\/li>\n<li><code>k<\/code>\u00a0is in the range of\u00a0<code>[0, n - 1]<\/code>.<\/li>\n<li>There\u00a0will\u00a0not\u00a0be\u00a0any\u00a0duplicated\u00a0flights or\u00a0self\u00a0cycles.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1854\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/787-ep170.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/787-ep170.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/787-ep170-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/02\/787-ep170-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution 1: DFS<\/strong><\/h1>\n<p>w\/o prunning TLE<\/p>\n<p>w\/ prunning Accepted<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 36 ms\r\nclass Solution {\r\npublic:\r\n  int findCheapestPrice(int n, vector&lt;vector&lt;int&gt;&gt;&amp; flights, int src, int dst, int K) {\r\n    g_.clear();  \r\n    for (const auto&amp; e : flights)\r\n      g_[e[0]].emplace_back(e[1], e[2]);\r\n    vector&lt;int&gt; visited(n, 0);\r\n    visited[src] = 1;\r\n    int ans = INT_MAX;\r\n    dfs(src, dst, K + 1, 0, visited, ans);\r\n    return ans == INT_MAX ? - 1 : ans;\r\n  }\r\nprivate:\r\n  unordered_map&lt;int, vector&lt;pair&lt;int,int&gt;&gt;&gt; g_;\r\n  \r\n  void dfs(int src, int dst, int k, int cost, vector&lt;int&gt;&amp; visited, int&amp; ans) {\r\n    if (src == dst) {\r\n      ans = cost;\r\n      return;\r\n    }\r\n    \r\n    if (k == 0) return;    \r\n    \r\n    for (const auto&amp; p : g_[src]) {\r\n      if (visited[p.first]) continue; \/\/ do not visit the same city twice.\r\n      if (cost + p.second &gt; ans) continue; \/\/ IMPORTANT!!! prunning \r\n      visited[p.first] = 1;\r\n      dfs(p.first, dst, k - 1, cost + p.second, visited, ans);\r\n      visited[p.first] = 0;\r\n    }\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: BFS<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 20 ms\r\nclass Solution {\r\npublic:\r\n  int findCheapestPrice(int n, vector&lt;vector&lt;int&gt;&gt;&amp; flights, int src, int dst, int K) {\r\n    unordered_map&lt;int, vector&lt;pair&lt;int,int&gt;&gt;&gt; g;\r\n    for (const auto&amp; e : flights)\r\n      g[e[0]].emplace_back(e[1], e[2]);\r\n    \r\n    int ans = INT_MAX;\r\n    queue&lt;pair&lt;int,int&gt;&gt; q;\r\n    q.push({src, 0});\r\n    int steps = 0;\r\n    \r\n    while (!q.empty()) {\r\n      int size = q.size();\r\n      while (size--) {\r\n        int curr = q.front().first;\r\n        int cost = q.front().second;\r\n        q.pop();\r\n        if (curr == dst) \r\n          ans = min(ans, cost);\r\n        for (const auto&amp; p : g[curr]) {\r\n          if (cost + p.second &gt; ans) continue; \/\/ Important: prunning          \r\n          q.push({p.first, cost + p.second});\r\n        }\r\n      }\r\n      if (steps++ &gt; K) break;\r\n    }\r\n    \r\n    return ans == INT_MAX ? - 1 : ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 3: Bellman-Ford algorithm<\/strong><\/h1>\n<p>dp[k][i]: min cost from src to i taken up to k flights (k-1 stops)<\/p>\n<p>init: dp[0:k+2][src] = 0<\/p>\n<p>transition: dp[k][i] = min(dp[k-1][j] + price[j][i])<\/p>\n<p>ans: dp[K+1][dst]<\/p>\n<p>Time complexity: O(k * |flights|) \/ O(k*n^2)<\/p>\n<p>Space complexity: O(k*n) -&gt; O(n)<\/p>\n<p>w\/o space compression O(k*n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ O(k*n)<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 15 ms\r\nclass Solution {\r\npublic:\r\n  int findCheapestPrice(int n, vector&lt;vector&lt;int&gt;&gt;&amp; flights, int src, int dst, int K) {\r\n    constexpr int kInfCost = 1e9;\r\n    vector&lt;vector&lt;int&gt;&gt; dp(K + 2, vector&lt;int&gt;(n, kInfCost));\r\n    dp[0][src] = 0;\r\n    \r\n    for (int i = 1; i &lt;= K + 1; ++i) {\r\n      dp[i][src] = 0;\r\n      for (const auto&amp; p : flights)\r\n          dp[i][p[1]] = min(dp[i][p[1]], dp[i-1][p[0]] + p[2]);    \r\n    }\r\n    \r\n    return dp[K + 1][dst] &gt;= kInfCost ? -1 : dp[K + 1][dst];\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ O(n)<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 12 ms\r\nclass Solution {\r\npublic:\r\n  int findCheapestPrice(int n, vector&lt;vector&lt;int&gt;&gt;&amp; flights, int src, int dst, int K) {\r\n    constexpr int kInfCost = 1e9;\r\n    vector&lt;int&gt; cost(n, kInfCost);\r\n    cost[src] = 0;\r\n    \r\n    for (int i = 0; i &lt;= K; ++i) {\r\n      vector&lt;int&gt; tmp(cost);\r\n      for (const auto&amp; p : flights)\r\n          tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2]);      \r\n      cost.swap(tmp);\r\n    }\r\n    \r\n    return cost[dst] &gt;= kInfCost ? -1 : cost[dst];\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 11 ms\r\nclass Solution {\r\n  public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {\r\n    final int kInfCost = 1&lt;&lt;30;\r\n    int[] cost = new int[n];\r\n    Arrays.fill(cost, kInfCost);\r\n    cost[src] = 0;\r\n    \r\n    for (int i = 0; i &lt;= K; ++i) {\r\n      int[] tmp = cost.clone();\r\n      for(int[] p: flights)\r\n        tmp[p[1]] = Math.min(tmp[p[1]], cost[p[0]] + p[2]);\r\n      cost = tmp;\r\n    }\r\n    \r\n    return cost[dst] &gt;= kInfCost ? -1 : cost[dst]; \r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 132 ms\r\n\"\"\"\r\nclass Solution:\r\n  def findCheapestPrice(self, n, flights, src, dst, K):\r\n    kInfCost = 1e9\r\n    cost = [kInfCost for _ in range(n)]\r\n    cost[src] = 0\r\n    \r\n    for i in range(K + 1):\r\n      tmp = list(cost)\r\n      for p in flights:\r\n        tmp[p[1]] = min(tmp[p[1]], cost[p[0]] + p[2])\r\n      cost = tmp\r\n    \r\n    return -1 if cost[dst] &gt;= 1e9 else cost[dst]<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u57ce\u5e02\u4e4b\u95f4\u7684\u673a\u7968\u4ef7\u683c\uff0c\u95ee\u4ecesrc\u5230dst\u7684\u6700\u5c11\u9700\u8981\u82b1\u591a\u5c11\u94b1\uff0c\u6700\u591a\u53ef\u4ee5\u4e2d\u8f6ck\u4e2a\u673a\u573a\u3002 There are\u00a0n\u00a0cities connected by\u00a0m\u00a0flights. Each fight starts from city\u00a0u\u00a0and arrives at\u00a0v\u00a0with a price\u00a0w. Now given all the cities and fights, together with starting city\u00a0src\u00a0and&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[221,34,33,18,177,87],"class_list":["post-1842","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-bellman-ford","tag-bfs","tag-dfs","tag-dp","tag-medium","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1842","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=1842"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1842\/revisions"}],"predecessor-version":[{"id":3793,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1842\/revisions\/3793"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1842"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1842"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1842"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}