Loading page…
Practice problem · easy
A food delivery app plans every courier's trip. The city has n junctions, numbered 0 to n - 1, and the roads between them are one-way. Each road takes some minutes to ride, and no road takes less than a minute.
You work on the route planner. The app knows where the courier picks up the food and where the customer lives. It shows the fewest minutes the trip can take, or says that there is no way to get there.
Write cheapest_route(n, roads, start, target).
n is the number of junctions.roads[i] = [a, b, minutes] is a one-way road from junction a to junction b that takes minutes minutes. Two junctions can have several roads, and each road is listed once.start is the pickup junction and target is the customer's junction.start to target. Return -1 when target cannot be reached. When start equals target, return 0.Input: n = 5, roads = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5]], start = 0, target = 3
Output: 4Dijkstra keeps a heap of (minutes so far, junction) entries and always takes the smallest.
| Taken from the heap | Roads relaxed | Heap after |
|---|---|---|
| (0, junction 0) | 0 to 1 gives 4, 0 to 2 gives 1 | (1, 2), (4, 1) |
| (1, junction 2) | 2 to 1 gives 3, 2 to 3 gives 6 | (3, 1), (4, 1), (6, 3) |
| (3, junction 1) | 1 to 3 gives 4 | (4, 1), (4, 3), (6, 3) |
| (4, junction 1) | stale: junction 1 already has 3 | (4, 3), (6, 3) |
| (4, junction 3) | the target: stop |
The cheapest trip goes 0, 2, 1, 3 and takes 1 + 2 + 1 = 4 minutes.
Input: n = 3, roads = [[0, 1, 2]], start = 0, target = 2
Output: -1No road leads to junction 2, so the heap runs dry before the target.
Input: n = 1, roads = [], start = 0, target = 0
Output: 0The courier is already at the customer's junction.
1 ≤ n ≤ 100,0000 ≤ len(roads) ≤ 200,000, and every road is [a, b, minutes] with 0 ≤ a, b < n, a ≠ b and 1 ≤ minutes ≤ 1,0000 ≤ start, target < nThere can be 100,000 junctions and 200,000 roads. Dijkstra with a heap does about one heap operation per road, so around 200,000 × 17 steps, which is a few million. Passing over all the roads again and again until nothing improves can need one pass per road on a long chain, which is 200,000 × 100,000 steps. That is far too slow.
cheapest_route · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.