Depot Delivery Distances
EasyAdvanced GraphsFree
Problem
A courier company has n drop points numbered 0 to n - 1. Each entry roads[i] = [u, v, w] is a one-way road from u to v that takes w minutes. Vans leave the depot at drop point source.
Return an array dist of length n where dist[i] is the minimum number of minutes needed to reach drop point i from the depot, or -1 if it cannot be reached at all.
Example 1
- Input:
- n = 4, roads = [[0,1,4],[0,2,1],[2,1,2],[1,3,1]], source = 0
- Output:
- [0, 3, 1, 4]
Going 0 → 2 → 1 costs 1 + 2 = 3, cheaper than the direct road of 4. Point 3 is then reached at 3 + 1 = 4.
Example 2
- Input:
- n = 3, roads = [[0,1,5]], source = 1
- Output:
- [-1, 0, -1]
Road 0 → 1 is one-way, so nothing is reachable from 1.
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ roads.length ≤ 2·10^4
- 0 ≤ w ≤ 10^4
- Parallel roads may exist.
Hint
Show the first hint
All travel times are non-negative. Which classic algorithm finalises nodes in increasing order of distance?
Walkthrough
How to approach it
01Clarify before coding
- Are the roads directed? Yes, each road is one-way.
- Can a travel time be 0 or negative? It can be 0, never negative, so Dijkstra is valid.
- What about unreachable points? Report -1 for them; the source itself is 0.
- Can there be several roads between the same pair? Yes; relaxation naturally keeps the cheapest.
02Brute force
Run Bellman-Ford: relax every road n - 1 times.
Cost: O(n · E) = 10^4 · 2·10^4 = 2·10^8 relaxations in the worst case, far too slow when Dijkstra does the same job in O(E log n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.