Minimum Score of a Path Between Two Cities

A path's score is the minimum edge weight along that path. Given a connected road network, return the minimum possible score of any path from city 1 to city n. Pattern focus: Kruskal/Union-Find. Explore the connected component that contains city 1 and find the smallest edge inside it.

Input Format

n = number of cities, roads = bidirectional roads [city1, city2, distance]

Output Format

minimum possible score of any path from city 1 to city n

Constraints

  • 1 <= n <= 10^5
  • 1 <= roads.length <= 2 * 10^5
  • 1 <= city1, city2 <= n
  • 1 <= distance <= 10^9

Examples

Example 1:

Input:

n = 4
roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]

Output:

5

Explanation:

Among all paths from 1 to 4, the best score is 5.

Example 2:

Input:

n = 3
roads = [[1,2,2],[2,3,4],[1,3,3]]

Output:

2

Explanation:

The path 1-2-3 has minimum edge 2, which is the best possible.

Example 3:

Input:

n = 5
roads = [[1,2,10],[2,5,8],[1,3,7],[3,4,6],[4,5,5]]

Output:

5

Explanation:

The connected component from city 1 contains an edge of weight 5, which becomes the answer.

Loading...
Minimum Score of a Path Between Two Cities