{"id":10044,"date":"2023-04-30T11:03:03","date_gmt":"2023-04-30T18:03:03","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=10044"},"modified":"2023-04-30T21:41:52","modified_gmt":"2023-05-01T04:41:52","slug":"leetcode-2662-minimum-cost-of-a-path-with-special-roads","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-2662-minimum-cost-of-a-path-with-special-roads\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2662. Minimum Cost of a Path With Special Roads"},"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 2662. Minimum Cost of a Path With Special Roads - \u5237\u9898\u627e\u5de5\u4f5c EP411\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/oBtS4aAJDaA?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>You are given an array&nbsp;<code>start<\/code>&nbsp;where&nbsp;<code>start = [startX, startY]<\/code>&nbsp;represents your initial position&nbsp;<code>(startX, startY)<\/code>&nbsp;in a 2D space. You are also given the array&nbsp;<code>target<\/code>&nbsp;where&nbsp;<code>target = [targetX, targetY]<\/code>&nbsp;represents your target position&nbsp;<code>(targetX, targetY)<\/code>.<\/p>\n\n\n\n<p>The cost of going from a position&nbsp;<code>(x1, y1)<\/code>&nbsp;to any other position in the space&nbsp;<code>(x2, y2)<\/code>&nbsp;is&nbsp;<code>|x2 - x1| + |y2 - y1|<\/code>.<\/p>\n\n\n\n<p>There are also some special roads. You are given a 2D array&nbsp;<code>specialRoads<\/code>&nbsp;where&nbsp;<code>specialRoads[i] = [x1<sub>i<\/sub>, y1<sub>i<\/sub>, x2<sub>i<\/sub>, y2<sub>i<\/sub>, cost<sub>i<\/sub>]<\/code>&nbsp;indicates that the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;special road can take you from&nbsp;<code>(x1<sub>i<\/sub>, y1<sub>i<\/sub>)<\/code>&nbsp;to&nbsp;<code>(x2<sub>i<\/sub>, y2<sub>i<\/sub>)<\/code>&nbsp;with a cost equal to&nbsp;<code>cost<sub>i<\/sub><\/code>. You can use each special road any number of times.<\/p>\n\n\n\n<p>Return&nbsp;<em>the minimum cost required to go from<\/em>&nbsp;<code>(startX, startY)<\/code>&nbsp;to&nbsp;<code>(targetX, targetY)<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong> The optimal path from (1,1) to (4,5) is the following:\n- (1,1) -&gt; (1,2). This move has a cost of |1 - 1| + |2 - 1| = 1.\n- (1,2) -&gt; (3,3). This move uses the first special edge, the cost is 2.\n- (3,3) -&gt; (3,4). This move has a cost of |3 - 3| + |4 - 3| = 1.\n- (3,4) -&gt; (4,5). This move uses the second special edge, the cost is 1.\nSo the total cost is 1 + 2 + 1 + 1 = 5.\nIt can be shown that we cannot achieve a smaller total cost than 5.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]\n<strong>Output:<\/strong> 7\n<strong>Explanation:<\/strong> It is optimal to not use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>start.length == target.length == 2<\/code><\/li><li><code>1 &lt;= startX &lt;= targetX &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= startY &lt;= targetY &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= specialRoads.length &lt;= 200<\/code><\/li><li><code>specialRoads[i].length == 5<\/code><\/li><li><code>startX &lt;= x1<sub>i<\/sub>, x2<sub>i<\/sub> &lt;= targetX<\/code><\/li><li><code>startY &lt;= y1<sub>i<\/sub>, y2<sub>i<\/sub> &lt;= targetY<\/code><\/li><li><code>1 &lt;= cost<sub>i<\/sub> &lt;= 10<sup>5<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Dijkstra<\/strong><\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li>Create a node for each point in special edges as well as start and target. <\/li><li>Add edges for special roads (note it&#8217;s directional)<\/li><li>Add edges for each pair of node with default cost, i.e. |x1-x2| + |y1-y2|<\/li><li>Run Dijkstra&#8217;s algorithm<\/li><\/ol>\n\n\n\n<p>Time complexity: O(n<sup>2<\/sup>logn)<br>Space complexity: O(n<sup>2<\/sup>)<\/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 minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {\n    unordered_map<long, int> ids;\n    vector<pair<int, int>> pos;\n    \n    auto getId = [&](int x, int y) {\n      const auto key = ((unsigned long)x << 32) | y;\n      if (ids.count(key)) return ids[key];\n      const int id = ids.size();      \n      ids[key] = id;\n      pos.emplace_back(x, y);\n      return id;\n    };\n    const int s = getId(start[0], start[1]);\n    const int t = getId(target[0], target[1]);\n    vector<vector<pair<int, int>>> g;\n    auto addEdge = [&](int x1, int y1, int x2, int y2, int c = INT_MAX) {      \n      int n1 = getId(x1, y1);\n      int n2 = getId(x2, y2);\n      if (n1 == n2) return;\n      while (g.size() <= max(n1, n2)) g.push_back({});      \n      int cost = min(c, abs(x1 - x2) + abs(y1 - y2));\n      g[n1].emplace_back(cost, n2);\n      \/\/ directional for special edge\n      if (c == INT_MAX) g[n2].emplace_back(cost, n1);\n    };\n    for (const auto&#038; r : specialRoads)\n      addEdge(r[0], r[1], r[2], r[3], r[4]);    \n    for (int i = 0; i < pos.size(); ++i)\n      for (int j = i + 1; j < pos.size(); ++j)\n        addEdge(pos[i].first, pos[i].second, \n                pos[j].first, pos[j].second);\n    vector<int> dist(ids.size(), INT_MAX);\n    dist[s] = 0;\n    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;\n    q.emplace(0, s);    \n    while (!q.empty()) {\n      auto [d, u] = q.top(); q.pop();\n      if (d > dist[u]) continue;\n      if (u == t) return d;\n      for (auto [c, v] : g[u])\n        if (d + c < dist[v])\n          q.emplace(dist[v] = d + c, v);\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array&nbsp;start&nbsp;where&nbsp;start = [startX, startY]&nbsp;represents your initial position&nbsp;(startX, startY)&nbsp;in a 2D space. You are also given the array&nbsp;target&nbsp;where&nbsp;target = [targetX, targetY]&nbsp;represents your&#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,77,177,87],"class_list":["post-10044","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dijkstra","tag-graph","tag-medium","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10044","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=10044"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10044\/revisions"}],"predecessor-version":[{"id":10047,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/10044\/revisions\/10047"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=10044"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=10044"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=10044"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}