All-Pairs Travel Table
EasyAdvanced GraphsFree
Problem
A regional bus office wants to print a table of travel times between all of its n stops. Each roads[i] = [u, v, w] is a one-way service from stop u to stop v that takes w minutes.
Return an n × n matrix table where table[i][j] is the fastest travel time from stop i to stop j, 0 on the diagonal, and -1 when j cannot be reached from i.
Example 1
- Input:
- n = 3, roads = [[0,1,4],[1,2,1],[0,2,7]]
- Output:
- [[0,4,5],[-1,0,1],[-1,-1,0]]
From 0 to 2, going through 1 takes 4 + 1 = 5, faster than the direct 7.
Example 2
- Input:
- n = 2, roads = []
- Output:
- [[0,-1],[-1,0]]
Constraints
- 1 ≤ n ≤ 150
- 0 ≤ roads.length ≤ n·(n - 1)·2
- 0 ≤ w ≤ 10^5
- Parallel services may exist.
Hint
Show the first hint
You need every source, and n is tiny. Is there a simple triple loop that handles all pairs at once?
Walkthrough
How to approach it
01Clarify before coding
- Directed or undirected? Directed: a service from u to v says nothing about v to u.
- Can weights be negative? No, they are between 0 and 10^5.
- What goes on the diagonal? 0, even if there is a cycle back to the same stop.
02Brute force
Run Dijkstra from each of the n stops.
Cost: O(n · E log n). It works, but with E up to ~n² it is more code and no faster than the O(n³) triple loop for n = 150.
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.