#2492
Minimum Score of a Path Between Two Cities
specialist · 750 · lc medium +31 · verified · 58.6% accepted · 1,906 likes · top 55%
Description
Given n cities (numbered 1 to n) and a bidirectional road list roads where each entry [ai, bi, distancei] gives a road's endpoints and length, find the minimum possible score of any path from city 1 to city n. A path's score is the minimum edge distance along the path. Roads may be traversed multiple times and cities may be revisited.
Example 1:
Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.
Example 2:
Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
Output: 2
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.
Code
1
2
3