2492. Minimum Score of a Path Between Two Cities

You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. The cities graph is not necessarily connected.

The score of a path between two cities is defined as the minimum distance of a road in this path.

Return the minimum possible score of a path between cities 1 and n.

Note:

A path is a sequence of roads between two cities.
It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
The test cases are generated such that there is at least one path between 1 and n.

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.

Solution

Approach 1: just find that min edge in the connected component containing node 1.

Code (Python)

Approach 1:

from collections import defaultdict
class Solution:
    def minScore(self, n: int, roads: list[list[int]]) -> int:
        # just find that min edge in the connected component containing node 1
        edges = defaultdict(list)
        for end1, end2, value in roads:
            edges[end1].append((end2, value))
            edges[end2].append((end1, value))

        min_edge = [float('inf')]
        self._recurse(1, edges, set(), min_edge)
        return min_edge[0]
    
    def _recurse(self, node, edges, seen, min_edge):
        if node in seen:
            return
        seen.add(node)
        for neighbor, value in edges[node]:
            min_edge[0] = min(min_edge[0], value)
            self._recurse(neighbor, edges, seen, min_edge)

Approach 2:

Code (C++)

Approach 1:

Approach 2: