Parcel With Few Handoffs
You run a small pottery shop and ship a fragile vase through a network of courier depots. Each route between two depots is run by a different small firm, goes one way only, and has its own fee. Chaining cheap routes together is usually the best deal.
But every time the parcel stops at a depot in between, it is unloaded and reloaded, and that is when vases break. So you allow at most maxStops stops between the depot where you drop it off and the depot where the buyer collects it. What is the cheapest way to send it under that rule?
Your task
Write cheapestDelivery(n, routes, origin, dest, maxStops). Depots are numbered 0 to n - 1. Each [a, b, fee] in routes is a one-way route from depot a to depot b. Return the lowest total fee to get from origin to dest passing through at most maxStops depots in between.
A direct route has 0 stops. A trip using 3 routes has 2 stops. Return -1 if no trip within the limit exists.
cheapestDelivery(n: int, routes: int[][], origin: int, dest: int, maxStops: int) → int
Examples
n = 4 routes = [[0, 1, 10], [1, 2, 10], [2, 3, 10], [0, 3, 50], [0, 2, 25]] origin = 0 dest = 3 maxStops = 1
35
The cheapest trip overall is 0 → 1 → 2 → 3 for 30, but it stops twice. With at most 1 stop, the choices are 0 → 3 for 50 and 0 → 2 → 3 for 35. The answer is 35.
n = 3 routes = [[0, 1, 5], [1, 2, 5]] origin = 0 dest = 2 maxStops = 0
-1
The only trip stops at depot 1, and no stops are allowed. Return -1.
Constraints
- 2 ≤ n ≤ 100
- 0 ≤ routes.length ≤ 2,000
- 0 ≤ a, b < n and a ≠ b; no route is listed twice
- 1 ≤ fee ≤ 10,000
- origin ≠ dest
- 0 ≤ maxStops < n
Start with brute force
Try every trip of up to maxStops + 1 routes with a depth-first search, and keep the cheapest that ends at dest. With many routes out of each depot, the number of trips grows like (routes per depot)stops, so a dense network with 99 allowed stops is far out of reach.
Plain Dijkstra is fast but wrong here. It keeps only the cheapest fee per depot and throws away a pricier path that used fewer stops, which may be the only one still allowed to reach dest.
Hints
0 of 4 shown- Hint 1
In the first example, what is the cheapest fee to reach each depot using exactly 1 route? Using at most 2 routes? How does the second list follow from the first?
- Hint 2
"At most k stops" is the same as "at most k + 1 routes". Think in rounds: after round r, you know the cheapest fee to every depot using at most r routes.
- Hint 3
To go from round r to round r + 1, try extending every round-r trip by one more route. There is a trap: if you update the fees in place while going through the routes, a single round can chain several routes. How do you prevent that?
- Hint 4
Run Bellman-Ford for exactly
maxStops + 1rounds. In each round, copy the current fee array, then for every route[a, b, fee]updatecopy[b]using the old value ofa. Replace the array with the copy at the end of the round. The answer is the fee atdest, or -1 if it is still infinite.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
The limit on stops is really a limit on the number of routes: at most maxStops + 1. Bellman-Ford naturally counts routes. Each round extends every known trip by one route, so after round r the array holds the cheapest fee using at most r routes. Stop after maxStops + 1 rounds.
Trace the first example with maxStops = 1, so 2 rounds. Fees start as [0, ∞, ∞, ∞].
- Round 1, reading [0, ∞, ∞, ∞]. From depot 0: depot 1 = 10, depot 3 = 50, depot 2 = 25. Routes out of 1 and 2 are skipped because their old fees are ∞. Result [0, 10, 25, 50].
- Round 2, reading [0, 10, 25, 50]. 1 → 2 gives 20, better than 25. 2 → 3 gives 25 + 10 = 35, better than 50. Result [0, 10, 20, 35].
The answer is 35. Notice that round 2 used depot 2's old fee, 25, not the fresh 20. The 20 comes from 0 → 1 → 2, which already used 2 routes, so adding 2 → 3 would make 3 routes. Reading from the old array is exactly what enforces the limit.
That copy is the whole difficulty. Update in place and, when routes happen to be listed in path order, one round can run along a whole chain. The test with routes 0→1→2→3 and no stops allowed catches it: in place, you would return 3 instead of 100.
function cheapestDelivery(n, routes, origin, dest, maxStops) {
let best = new Array(n).fill(Infinity);
best[origin] = 0;
// round r: cheapest fee using at most r routes
for (let round = 1; round <= maxStops + 1; round++) {
const next = best.slice(); // read from best, write to next
for (const [a, b, fee] of routes) {
if (best[a] === Infinity) continue;
if (best[a] + fee < next[b]) next[b] = best[a] + fee;
}
best = next;
}
return best[dest] === Infinity ? -1 : best[dest];
}def cheapest_delivery(n, routes, origin, dest, max_stops):
INF = float('inf')
best = [INF] * n
best[origin] = 0
# round r: cheapest fee using at most r routes
for _ in range(max_stops + 1):
nxt = best[:] # read from best, write to nxt
for a, b, fee in routes:
if best[a] != INF and best[a] + fee < nxt[b]:
nxt[b] = best[a] + fee
best = nxt
return -1 if best[dest] == INF else best[dest]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.