2492. Minimum Score of a Path Between Two Cities

BFS
DFS
Union Find
Graph

TIME

O(n + m)

SPACE

O(n + m)

Intuition

The scoring rule plus the freedom to reuse roads and revisit cities changes the problem completely. A path's score is its minimum edge, and since you can wander anywhere in the connected component and backtrack, any road in city 1's component can be included in some path from 1 to n (walk to that road, cross it, return, then head to n). City n is guaranteed to be in the same component.

So the minimum achievable score is just the smallest edge weight among all roads in city 1's connected component.

Approach

Build an adjacency list (store neighbor + distance).
BFS/DFS from city 1, visiting every reachable node.
Track the minimum distance of every edge encountered during the traversal.
Return that minimum.

(Union-Find gives the same result: union all roads, then take the min edge whose endpoints share city 1's root.)

Complexity

Time: O(n + m)
Space: O(n + m), adjacency list and visited set

Edge Cases

Direct edge 1 - n still just contributes to the component min
Roads in other disconnected components are irrelevant and never visited
A road can be traversed multiple times, so revisiting doesn't change the min logic
The component always contains both 1 and n (guaranteed by constraints)

Code

from typing import List
from collections import deque


class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        """
        2492. Minimum Score of a Path Between Two Cities
        Time: O(n + m)
        Space: O(n + m)
        """
        adj = [[] for _ in range(n + 1)]
        for a, b, d in roads:
            adj[a].append((b, d))
            adj[b].append((a, d))

        ans = float("inf")
        visited = [False] * (n + 1)
        visited[1] = True
        dq = deque([1])
        while dq:
            u = dq.popleft()
            for v, d in adj[u]:
                ans = min(ans, d)
                if not visited[v]:
                    visited[v] = True
                    dq.append(v)
        return ans

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * 2492. Minimum Score of a Path Between Two Cities
 * Time: O(n + m)
 * Space: O(n + m)
 */
class Solution {
    public int minScore(int n, int[][] roads) {
        List<int[]>[] adj = new List[n + 1];
        for (int i = 1; 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]});
        }

        int ans = Integer.MAX_VALUE;
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.add(1);
        while (!dq.isEmpty()) {
            int u = dq.poll();
            for (int[] nb : adj[u]) {
                ans = Math.min(ans, nb[1]);
                if (!visited[nb[0]]) {
                    visited[nb[0]] = true;
                    dq.add(nb[0]);
                }
            }
        }
        return ans;
    }
}