Minimum Score of a Path Between Two Cities
01 · Problem
There are n cities numbered 1 to n. Each roads[i] = [a, b, d] is a two-way road between cities a and b with distance d. The road network may be disconnected.
The score of a path is the smallest distance of any road on that path. A path may revisit cities and reuse roads any number of times, and it may pass through cities 1 and n more than once.
Return the minimum possible score of any path between city 1 and city n. It is guaranteed that at least one path between them exists.
02 · Examples
n = 4, roads = [[1,2,8],[2,4,6],[2,3,3]]
3
Walk 1 -> 2 -> 3 -> 2 -> 4. The detour to city 3 uses the road of length 3, so the score is 3.
n = 5, roads = [[1,5,10],[2,3,1],[1,4,7]]
7
Cities 2 and 3 are not connected to city 1, so their road cannot be used. Using 1 -> 4 -> 1 -> 5 gives score 7.
n = 2, roads = [[1,2,5]]
5
The only road joins the two cities directly, so the score is 5.
03 · Constraints
- 012 <= n <= 105
- 021 <= roads.length <= 105
- 03roads[i].length == 3, 1 <= a, b <= n, a != b
- 041 <= d <= 104
- 05No duplicate roads, and cities 1 and n are connected
04 · Optimal complexity
- Time
- O(n + m)
- Space
- O(n + m)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.