Minimum Score of a Path Between Two Cities

medium graph bfs union find

Problem

Given an undirected weighted graph of n cities (1..n) and roads, the "score" of a path is the minimum edge weight on it. Return the smallest possible score over all paths from city 1 to city n. Paths may revisit edges/nodes, so the answer is the minimum edge weight in the connected component of city 1.

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

Output5

All four cities are connected; the minimum edge weight is 5.

roads (u,v,w;...)

from collections import deque

def min_score(n, roads):
    adj = [[] for _ in range(n + 1)]
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))
    seen = [False] * (n + 1)
    q = deque([1])
    seen[1] = True
    ans = float("inf")
    while q:
        u = q.popleft()
        for v, w in adj[u]:
            ans = min(ans, w)
            if not seen[v]:
                seen[v] = True
                q.append(v)
    return ans

function minScore(n, roads) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of roads) { adj[u].push([v, w]); adj[v].push([u, w]); }
  const seen = new Array(n + 1).fill(false);
  const q = [1];
  seen[1] = true;
  let ans = Infinity;
  while (q.length) {
    const u = q.shift();
    for (const [v, w] of adj[u]) {
      ans = Math.min(ans, w);
      if (!seen[v]) { seen[v] = true; q.push(v); }
    }
  }
  return ans;
}

class Solution {
    public int minScore(int n, int[][] roads) {
        List<int[]>[] adj = new List[n + 1];
        for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
        for (int[] r : roads) {
            adj[r[0]].add(new int[]{ r[1], r[2] });
            adj[r[1]].add(new int[]{ r[0], r[2] });
        }
        boolean[] seen = new boolean[n + 1];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(1); seen[1] = true;
        int ans = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] e : adj[u]) {
                ans = Math.min(ans, e[1]);
                if (!seen[e[0]]) { seen[e[0]] = true; q.offer(e[0]); }
            }
        }
        return ans;
    }
}

int minScore(int n, vector<vector<int>>& roads) {
    vector<vector<pair<int,int>>> adj(n + 1);
    for (auto& r : roads) {
        adj[r[0]].push_back({ r[1], r[2] });
        adj[r[1]].push_back({ r[0], r[2] });
    }
    vector<bool> seen(n + 1, false);
    queue<int> q;
    q.push(1); seen[1] = true;
    int ans = INT_MAX;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& [v, w] : adj[u]) {
            ans = min(ans, w);
            if (!seen[v]) { seen[v] = true; q.push(v); }
        }
    }
    return ans;
}

Explanation

The key insight is that a path is allowed to revisit edges and nodes. That means once you can reach a group of connected cities, you can walk over any edge inside that group as often as you like. So the smallest "score" of a path from city 1 to city n is just the lightest edge anywhere in city 1's connected component — city n doesn't even matter, because if the graph is connected they're in the same group.

So the algorithm is: explore the component that contains city 1 and remember the minimum edge weight seen along the way. The code uses a simple BFS from node 1 with a seen array.

While visiting a city u, we walk every edge (v, w) out of it and do ans = min(ans, w) — note we update the answer for every edge we touch, even ones leading to already-visited nodes, so no edge inside the component is missed. We still only enqueue unseen neighbors so the search terminates.

Example: n = 4, roads [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]. Starting at 1, BFS reaches all four cities, and the lightest edge it crosses has weight 5, so the answer is 5.

Because BFS visits the entire component and every incident edge, the final ans is the true minimum edge weight reachable from city 1.

Time: O(V + E) Space: O(V + E)