Solution

Method 1 – Dijkstra's Algorithm

Intuition

We treat each point (start, target, and all special road endpoints) as a node in a graph. The cost to move between any two points is the Manhattan distance, except for special roads, which have their own cost. Dijkstra's algorithm finds the shortest path from start to target efficiently.

Approach

Collect all unique points: start, target, and all special road endpoints.
Build edges:
- For every pair of points, add an edge with cost equal to their Manhattan distance.
- For each special road, add an edge from its start to its end with the given cost.
Use Dijkstra's algorithm:
- Start from the start point.
- Use a min-heap to always expand the lowest-cost node.
- Track the minimum cost to reach each point.
- Stop when reaching the target.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {\n        using P = pair<int, int>;\n        vector<P> pts = { {start[0], start[1]}, {target[0], target[1]} };\n        for (auto& r : specialRoads) {\n            pts.push_back({r[0], r[1]});\n            pts.push_back({r[2], r[3]});\n        }\n        unordered_map<int, unordered_map<int, int>> dist;\n        for (auto& p : pts) dist[p.first][p.second] = INT_MAX;\n        dist[start[0]][start[1]] = 0;\n        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;\n        pq.push({0, start[0], start[1]});\n        while (!pq.empty()) {\n            auto [cost, x, y] = pq.top(); pq.pop();\n            if (cost > dist[x][y]) continue;\n            int direct = abs(x - target[0]) + abs(y - target[1]);\n            if (dist[target[0]][target[1]] > cost + direct) {\n                dist[target[0]][target[1]] = cost + direct;\n                pq.push({cost + direct, target[0], target[1]});\n            }\n            for (auto& r : specialRoads) {\n                int d = abs(x - r[0]) + abs(y - r[1]) + r[4];\n                if (dist[r[2]][r[3]] > cost + d) {\n                    dist[r[2]][r[3]] = cost + d;\n                    pq.push({cost + d, r[2], r[3]});\n                }\n            }\n        }\n        return dist[target[0]][target[1]];\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minimumCost</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> start</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-da

Related Tags