Quietest Hub Town
MediumAdvanced Graphs
Problem
A logistics firm wants to place a warehouse in one of n towns joined by two-way roads roads[i] = [u, v, km]. To keep traffic low, it prefers the town from which the fewest other towns can be reached with a shortest route of at most limit kilometres.
Return that town. If several towns tie, return the one with the largest index.
Example 1
- Input:
- n = 4, roads = [[0,1,2],[1,2,3],[2,3,1],[0,3,9]], limit = 4
- Output:
- 0
Within 4 km: town 0 reaches {1}; town 1 reaches {0,2,3}; town 2 reaches {1,3}; town 3 reaches {1,2}. Town 0 has the fewest.
Example 2
- Input:
- n = 3, roads = [[0,1,1],[1,2,1]], limit = 1
- Output:
- 2
Towns 0 and 2 each reach one town; 2 has the larger index.
Constraints
- 2 ≤ n ≤ 100
- 0 ≤ roads.length ≤ n·(n - 1) / 2
- 1 ≤ km, limit ≤ 10^4
Hint
Show the first hint
You need shortest distances between every pair of towns.
Walkthrough
How to approach it
01Clarify before coding
- Is 'reachable' about one road or any route? Any route, by its shortest total length.
- Does a town count itself? No, only other towns.
- Tie-break? Largest index.
02Brute force
Run Dijkstra from every town.
Cost: O(n · E log n): fine as well, but more code than Floyd-Warshall for n = 100.
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.
This problem is part of Pro.