Minimum Cost of a Path With Special Roads — Solution
Minimum Cost of a Path With Special Roads solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Cost of a Path With Special Roads is a medium coding problem on arrays, graph and heap, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Graph, Heap, Shortest Path
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are at start = [startX, startY] on a grid of integer points and want to reach target = [targetX, targetY].
Walking from (x1, y1) to (x2, y2) costs |x2 - x1| + |y2 - y1|. In addition there are one-way special roads: specialRoads[i] = [x1, y1, x2, y2, cost] takes you from (x1, y1) to (x2, y2) for cost. Each special road may be used any number of times.
Return the minimum cost of getting from start to target.
Example 1
Input: start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
Output: 5
Explanation: Walk to (1,2) for 1, take road 0 to (3,3) for 2, walk to (3,4) for 1, take road 1 to (4,5) for 1: 1 + 2 + 1 + 1 = 5.
Example 2
Input: start = [3,2], target = [5,7], specialRoads = [[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
Output: 7
Explanation: No road beats walking straight there for |5 - 3| + |7 - 2| = 7.
Example 3
Input: start = [1,1], target = [10,4], specialRoads = [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]
Output: 8
Explanation: Walk to (1,2) for 1, take road 1 to (7,4) for 4, and walk to (10,4) for 3.
Constraints
start.length == target.length == 21 <= startX <= targetX <= 10^51 <= startY <= targetY <= 10^51 <= specialRoads.length <= 200specialRoads[i].length == 5startX <= x1, x2 <= targetXstartY <= y1, y2 <= targetY1 <= cost <= 10^5
Hints for Minimum Cost of a Path With Special Roads
Hint 1
Only a handful of points can matter: the start, the target and the two ends of each special road. Between them you simply walk, at Manhattan distance.
Hint 2
It is enough to stop at the end of each road: from any point, the next useful move is 'walk to the start of road i and take it', landing on road i's end.
Hint 3
That is a dense graph on at most 201 nodes — run Dijkstra in its simple
O(V²)array form, and for each settled node also try walking straight to the target.
How to solve Minimum Cost of a Path With Special Roads
The coordinates are huge but only 2k + 2 points are interesting. Model a node per road end plus the start; from any node you can 'walk to road i's start and ride it' to reach road i's end. Dijkstra over these nodes, finishing each with a straight walk to the target, gives the answer.
Approach
- Nodes: the start and the end
(x2, y2)of every road.dist[start] = 0, everything else infinite. - Repeat: pick the unsettled node
uwith the smallest distance and settle it. - Update the answer with
dist[u] + |u - target|. - For every road
i, relax its end withdist[u] + |u - (x1, y1)| + cost. - After all nodes are settled, return the answer.
Why it works
Any optimal route alternates walking and riding roads. Each ride ends at a road end, and walking legs can be merged (Manhattan distance obeys the triangle inequality), so the route is a sequence of 'walk to a road start, ride' steps between road ends, followed by one final walk. Those are exactly the edges Dijkstra relaxes, and all edge weights are non-negative.
Complexity
- Time —
O(k²) - Space —
O(k)
Pitfalls
- A special road can cost more than walking between its ends; the final walk and the free choice of edges cover that, so never force a road.
- Roads are one-way: only
(x1, y1) → (x2, y2). - The answer never exceeds the direct walk, at most
2 · 10^5, so 32-bit integers suffice.
Reference solution
Python
from typing import List
def minimumCost(start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
k = len(specialRoads)
# node 0 is the start, node i + 1 is the end of road i
px = [start[0]] + [r[2] for r in specialRoads]
py = [start[1]] + [r[3] for r in specialRoads]
INF = float("inf")
dist = [INF] * (k + 1)
dist[0] = 0
done = [False] * (k + 1)
best = abs(target[0] - start[0]) + abs(target[1] - start[1])
for _ in range(k + 1):
u = -1
for v in range(k + 1):
if not done[v] and (u < 0 or dist[v] < dist[u]):
u = v
if dist[u] == INF:
break
done[u] = True
best = min(best, dist[u] + abs(target[0] - px[u]) + abs(target[1] - py[u]))
for i, (x1, y1, _, _, cost) in enumerate(specialRoads):
cand = dist[u] + abs(x1 - px[u]) + abs(y1 - py[u]) + cost
if cand < dist[i + 1]:
dist[i + 1] = cand
return bestJava
public static int minimumCost(int[] start, int[] target, int[][] specialRoads) {
int k = specialRoads.length;
int[] px = new int[k + 1], py = new int[k + 1];
long[] dist = new long[k + 1];
boolean[] done = new boolean[k + 1];
px[0] = start[0]; py[0] = start[1];
for (int i = 0; i < k; i++) { px[i + 1] = specialRoads[i][2]; py[i + 1] = specialRoads[i][3]; }
Arrays.fill(dist, Long.MAX_VALUE);
dist[0] = 0;
long best = Math.abs(target[0] - start[0]) + Math.abs(target[1] - start[1]);
for (int it = 0; it <= k; it++) {
int u = -1;
for (int v = 0; v <= k; v++) if (!done[v] && (u < 0 || dist[v] < dist[u])) u = v;
if (dist[u] == Long.MAX_VALUE) break;
done[u] = true;
best = Math.min(best, dist[u] + Math.abs(target[0] - px[u]) + Math.abs(target[1] - py[u]));
for (int r = 0; r < k; r++) {
int[] road = specialRoads[r];
long cand = dist[u] + Math.abs(road[0] - px[u]) + Math.abs(road[1] - py[u]) + road[4];
if (cand < dist[r + 1]) dist[r + 1] = cand;
}
}
return (int) best;
}C++
int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
int k = specialRoads.size();
vector<long long> px(k + 1), py(k + 1), dist(k + 1, LLONG_MAX);
vector<bool> done(k + 1, false);
px[0] = start[0]; py[0] = start[1];
for (int i = 0; i < k; i++) { px[i + 1] = specialRoads[i][2]; py[i + 1] = specialRoads[i][3]; }
dist[0] = 0;
long long best = llabs(target[0] - start[0]) + llabs(target[1] - start[1]);
for (int it = 0; it <= k; it++) {
int u = -1;
for (int v = 0; v <= k; v++) if (!done[v] && (u < 0 || dist[v] < dist[u])) u = v;
if (dist[u] == LLONG_MAX) break;
done[u] = true;
best = min(best, dist[u] + llabs(target[0] - px[u]) + llabs(target[1] - py[u]));
for (int r = 0; r < k; r++) {
auto& road = specialRoads[r];
long long cand = dist[u] + llabs(road[0] - px[u]) + llabs(road[1] - py[u]) + road[4];
if (cand < dist[r + 1]) dist[r + 1] = cand;
}
}
return (int) best;
}JavaScript
var minimumCost = function(start, target, specialRoads) {
var k = specialRoads.length;
// node 0 is the start, node i + 1 is the end of road i
var px = [start[0]], py = [start[1]], dist = [0], done = [false];
for (var i = 0; i < k; i++) { px.push(specialRoads[i][2]); py.push(specialRoads[i][3]); dist.push(Infinity); done.push(false); }
var best = Math.abs(target[0] - start[0]) + Math.abs(target[1] - start[1]);
for (var it = 0; it <= k; it++) {
var u = -1;
for (var v = 0; v <= k; v++) if (!done[v] && (u < 0 || dist[v] < dist[u])) u = v;
if (dist[u] === Infinity) break;
done[u] = true;
best = Math.min(best, dist[u] + Math.abs(target[0] - px[u]) + Math.abs(target[1] - py[u]));
for (var r = 0; r < k; r++) {
var road = specialRoads[r];
var cand = dist[u] + Math.abs(road[0] - px[u]) + Math.abs(road[1] - py[u]) + road[4];
if (cand < dist[r + 1]) dist[r + 1] = cand;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Graph Data Structure