Course4all
Join us on telegram
Home/dsa/Union Find/Minimum Score of a Path Between Two Cities

Minimum Score of a Path Between Two Cities

Master this topic with zero to advance depth.

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 distancei. 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 city 1 and city n.

Insight

If cities 1 and n are connected, you can traverse any road in their connected component multiple times. Thus, the answer is simply the minimum weight road in the entire component containing city 1.

Medium

Examples

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Approach 1

Level I: DFS (Component Traversal)

Intuition

Since we can traverse any road in a connected component multiple times, the path score is simply the minimum weight of any road in the entire component that contains city 1 (and thus city n, if reachable). Use DFS to traverse the component and track the minimum weight encountered.

⏱ O(V + E).💾 O(V + E).
java
import java.util.*;
class Solution {
    public int minScore(int n, int[][] roads) {
        List<int[]>[] adj = new ArrayList[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[] min = {Integer.MAX_VALUE};
        dfs(adj, new boolean[n + 1], 1, min);
        return min[0];
    }
    private void dfs(List<int[]>[] adj, boolean[] vis, int u, int[] min) {
        vis[u] = true;
        for (int[] edge : adj[u]) {
            min[0] = Math.min(min[0], edge[1]);
            if (!vis[edge[0]]) dfs(adj, vis, edge[0], min);
        }
    }
}
Approach 2

Level III: Union-Find (Component Min Edge)

Intuition

Use DSU to maintain connected components and store the minimum edge weight seen so far for each component root.

⏱ O(E \cdot \alpha(N)).💾 O(N).
java
class Solution {
    public int minScore(int n, int[][] roads) {
        int[] p = new int[n+1]; for(int i=1; i<=n; i++) p[i]=i;
        int[] min = new int[n+1]; Arrays.fill(min, Integer.MAX_VALUE);
        for(int[] r : roads) {
            int r1 = find(p, r[0]), r2 = find(p, r[1]);
            p[r1] = r2;
            min[r2] = Math.min(r[2], Math.min(min[r1], min[r2]));
        }
        return min[find(p, 1)];
    }
    int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }
}
← Previous QuestionCritical Connections in a Network
Next Question →Remove Max Number of Edges to Keep Graph Fully Traversable