Minimum Score of a Path Between Two Cities

2492. Minimum Score of a Path Between Two Cities

Difficulty: Medium | Date: 2026-07-04

Patterns: Graphs | BFS | DFS Data Structures: Array

Problem

Given a connected weighted undirected graph of n cities and a list of roads (edges with weights), return the minimum score of any path between city 1 and city n. The score of a path is the minimum edge weight along it, and paths can revisit nodes and edges.

My Approach

Since paths can revisit nodes and edges, any edge in the connected component containing node 1 is reachable on some valid path to node n. So the problem reduces to finding the minimum edge weight in the entire connected component of node 1. I used BFS starting from city 1, tracking the minimum edge weight across every edge encountered.

Key Insight

Because you can revisit nodes and edges freely, the score is just the minimum edge weight in the connected component containing both node 1 and node n. No need to track paths - just explore the whole component.

Solution

BFS

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        adj_list = defaultdict(list)
        for a, b, dist in roads:
            adj_list[a].append((b, dist))
            adj_list[b].append((a, dist))
 
        seen = set()
        ans = 10**4
        q = deque([1])
        while q:
            node = q.popleft()
            if node in seen:
                continue
            seen.add(node)
            for neigh, dist in adj_list[node]:
                q.append(neigh)
                ans = min(ans, dist)
        return ans

DFS

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        adj_list = defaultdict(list)
        for a, b, dist in roads:
            adj_list[a].append((b, dist))
            adj_list[b].append((a, dist))
 
        seen = set()
        ans = [10**4]
 
        def dfs(node):
            seen.add(node)
            for neigh, dist in adj_list[node]:
                ans[0] = min(ans[0], dist)
                if neigh not in seen:
                    dfs(neigh)
 
        dfs(1)
        return ans[0]

Union Find

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        parent = list(range(n + 1))
 
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
 
        def union(x, y):
            parent[find(x)] = find(y)
 
        for a, b, _ in roads:
            union(a, b)
 
        ans = 10**4
        for a, b, dist in roads:
            if find(a) == find(1):
                ans = min(ans, dist)
        return ans

Complexity

• Time: O(N + E) - visit every node and edge once
• Space: O(N + E) - adjacency list storage

Prerequisites