# Minimum Score of a Path Between Two Cities
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities)
Canonical: https://scaleengineer.com/dsa/problems/minimum-score-of-a-path-between-two-cities
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-score-of-a-path-between-two-cities/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-score-of-a-path-between-two-cities/image1.png) 

**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.

**Constraints:**

* `2 <= n <= 105`
* `1 <= roads.length <= 105`
* `roads[i].length == 3`
* `1 <= ai, bi <= n`
* `ai != bi`
* `1 <= distancei <= 104`
* There are no repeated edges.
* There is at least one path between `1` and `n`.

# Approaches
## Graph Traversal (BFS/DFS)
The key insight is that since we can traverse any road multiple times, any path between two cities `u` and `v` can be extended to include any other road within the same connected component. This means the minimum score of a path between cities 1 and `n` is simply the minimum weight of any edge in the connected component that contains both 1 and `n`. We can find this component and the minimum edge weight by performing a graph traversal (like BFS or DFS) starting from city 1.
**Time:** O(n + roads.length). Building the adjacency list takes `O(roads.length)`. The BFS traversal visits each node and edge in the connected component of city 1 at most once. In the worst case, the graph is fully connected, leading to `O(n + roads.length)` time. · **Space:** O(n + roads.length). The adjacency list requires `O(roads.length)` space. The `visited` array takes `O(n)` space, and the BFS queue can take up to `O(n)` space in the worst case.
**Pros:** Conceptually straightforward, using a standard graph traversal algorithm.; Easy to implement.
**Cons:** Requires more space than the Union-Find approach due to the adjacency list, which can be significant if the number of roads is large.
### Explanation
We start by building an adjacency list representation of the graph from the `roads` array. Each entry in the adjacency list for a city `u` will store its neighbors and the distance to them.

We initialize a `minScore` variable to infinity and a `visited` array to keep track of the nodes we have already processed. We use a queue for a Breadth-First Search (BFS), starting with city 1.

In the BFS loop, we dequeue a city, and for each of its neighbors, we update `minScore` with the distance of the connecting road. If a neighbor hasn't been visited, we add it to the queue and mark it as visited.

The traversal continues until all reachable cities from city 1 have been visited. The final `minScore` will be the minimum edge weight in the entire connected component.

```java
class Solution {
    public int minScore(int n, int[][] roads) {
        // 1. Build adjacency list
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] road : roads) {
            adj.computeIfAbsent(road[0], k -> new ArrayList<>()).add(new int[]{road[1], road[2]});
            adj.computeIfAbsent(road[1], k -> new ArrayList<>()).add(new int[]{road[0], road[2]});
        }

        int minScore = Integer.MAX_VALUE;
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        // 2. Start BFS from city 1
        queue.offer(1);
        visited[1] = true;

        while (!queue.isEmpty()) {
            int city = queue.poll();

            if (!adj.containsKey(city)) {
                continue;
            }

            for (int[] neighborInfo : adj.get(city)) {
                int neighbor = neighborInfo[0];
                int distance = neighborInfo[1];

                // 3. Update minScore with every road in the component
                minScore = Math.min(minScore, distance);

                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }

        return minScore;
    }
}
```
### Algorithm
- Create an adjacency list `adj` where `adj[u]` contains pairs of `(v, distance)` for each road between `u` and `v`.
- Initialize a queue for BFS and add city `1`.
- Initialize a `visited` set or array and add `1` to it.
- Initialize `minScore = Integer.MAX_VALUE`.
- While the queue is not empty:
  - Dequeue the current city `u`.
  - For each neighbor `v` with distance `d` from `u`:
    - Update `minScore = min(minScore, d)`.
    - If `v` has not been visited, add `v` to the queue and the `visited` set.
- Return `minScore`.

## Union-Find (Disjoint Set Union)
This approach also relies on the fact that the answer is the minimum edge weight in the connected component of city 1. The Union-Find data structure is highly optimized for determining connected components. We can first use it to group all cities into components by processing each road. Then, we can find the component city 1 belongs to and iterate through the roads again to find the minimum weight road that connects two cities within that component.
**Time:** O(n + roads.length * α(n)), where `α(n)` is the inverse Ackermann function. Initializing the DSU takes `O(n)`. The first loop performs `roads.length` union operations, and the second loop performs `roads.length` find operations. With path compression, these operations take nearly constant time on average, `O(α(n))`.  · **Space:** O(n). The DSU data structure requires a `parent` array of size `n`, leading to `O(n)` space. This is more efficient than the BFS/DFS approach if the number of roads is large.
**Pros:** Excellent space efficiency, using only `O(n)` space.; Very fast, with nearly linear time complexity.
**Cons:** Requires two passes over the `roads` data.; The DSU data structure might be slightly less intuitive than a simple graph traversal for some.
### Explanation
We use a Disjoint Set Union (DSU) data structure, often implemented with a `parent` array, to keep track of the sets of connected cities.

First, we iterate through all the `roads`. For each road `[u, v, distance]`, we perform a `union` operation on cities `u` and `v`. This merges the sets they belong to, effectively building the connected components of the graph.

After processing all roads, the DSU structure correctly represents the components. We then find the representative of the component containing city 1 using the `find` operation.

Finally, we iterate through the `roads` array one more time. For each road, we check if one of its cities belongs to the same component as city 1 (by comparing their representatives). If it does, we update our `minScore` with the distance of that road.

```java
class DSU {
    private int[] parent;
    public DSU(int n) {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            parent[rootJ] = rootI;
        }
    }
}

class Solution {
    public int minScore(int n, int[][] roads) {
        DSU dsu = new DSU(n);
        // 1. Build components
        for (int[] road : roads) {
            dsu.union(road[0], road[1]);
        }

        int minScore = Integer.MAX_VALUE;
        // 2. Find min edge in the component of city 1
        for (int[] road : roads) {
            if (dsu.find(1) == dsu.find(road[0])) {
                minScore = Math.min(minScore, road[2]);
            }
        }

        return minScore;
    }
}
```
### Algorithm
- Initialize a DSU data structure for `n` cities.
- For each road `[u, v, d]` in `roads`:
  - Perform `union(u, v)`.
- Initialize `minScore = Integer.MAX_VALUE`.
- Find the representative of city 1's component: `root1 = find(1)`.
- For each road `[u, v, d]` in `roads`:
  - If `find(u)` is equal to `root1`, it means this road is in the same component.
  - Update `minScore = min(minScore, d)`.
- Return `minScore`.

# Solutions
### Java

```java
class Solution { private List < int []>[] g ; private boolean [] vis ; private int ans = 1 << 30 ; public int minScore ( int n , int [][] roads ) { g = new List [ n ]; vis = new boolean [ n ]; Arrays . setAll ( g , k -> new ArrayList <>()); for ( var e : roads ) { int a = e [ 0 ] - 1 , b = e [ 1 ] - 1 , d = e [ 2 ]; g [ a ]. add ( new int [] { b , d }); g [ b ]. add ( new int [] { a , d }); } dfs ( 0 ); return ans ; } private void dfs ( int i ) { for ( var nxt : g [ i ]) { int j = nxt [ 0 ], d = nxt [ 1 ]; ans = Math . min ( ans , d ); if (! vis [ j ]) { vis [ j ] = true ; dfs ( j ); } } } }
```

### JavaScript

```javascript
var minScore = function ( n , roads ) { // 构建点到点的映射表 const graph = Array . from ({ length : n + 1 }, () => new Map ()); for ( let [ u , v , w ] of roads ) { graph [ u ]. set ( v , w ); graph [ v ]. set ( u , w ); } // DFS const vis = new Array ( n ). fill ( false ); let ans = Infinity ; var dfs = function ( u ) { vis [ u ] = true ; for ( const [ v , w ] of graph [ u ]) { ans = Math . min ( ans , w ); if ( ! vis [ v ]) dfs ( v ); } }; dfs ( 1 ); return ans ; };
```

### CPP

```cpp
class Solution { public: int minScore ( int n , vector < vector < int >>& roads ) { vector < vector < pair < int , int >>> g ( n ); bool vis [ n ]; memset ( vis , 0 , sizeof vis ); for ( auto & e : roads ) { int a = e [ 0 ] - 1 , b = e [ 1 ] - 1 , d = e [ 2 ]; g [ a ]. emplace_back ( b , d ); g [ b ]. emplace_back ( a , d ); } int ans = INT_MAX ; function < void ( int ) > dfs = [ & ]( int i ) { for ( auto [ j , d ] : g [ i ]) { ans = min ( ans , d ); if ( ! vis [ j ]) { vis [ j ] = true ; dfs ( j ); } } }; dfs ( 0 ); return ans ; } };
```

### Python

```python
class Solution : def minScore ( self , n : int , roads : List [ List [ int ]]) -> int : def dfs ( i ): nonlocal ans for j , d in g [ i ]: ans = min ( ans , d ) if not vis [ j ]: vis [ j ] = True dfs ( j ) g = defaultdict ( list ) for a , b , d in roads : g [ a ]. append (( b , d )) g [ b ]. append (( a , d )) vis = [ False ] * ( n + 1 ) ans = inf dfs ( 1 ) return ans
```