> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Score of a Path Between Two Cities

> Tested Python solution for LeetCode 2492 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 2492, [Medium](/catalog/medium). Topics: [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Union-Find](/catalog/topics/union-find), [Graph Theory](/catalog/topics/graph-theory). [View on LeetCode](https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2492   # by problem number
lcpy gen -s minimum_score_of_a_path_between_two_cities   # by problem name
```

## 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`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2022/10/12/graph11.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.leetcode.com/uploads/2022/10/12/graph22.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 \<= 10^5
* 1 \<= roads.length \<= 10^5
* roads\[i].length == 3
* 1 \<= ai, bi \<= n
* ai != bi
* 1 \<= distancei \<= 10^4
* There are no repeated edges.
* There is at least one path between 1 and n.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_score_of_a_path_between_two_cities/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_score_of_a_path_between_two_cities/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n + m * alpha(m))
    # Space: O(n)
    def min_score(self, n: int, roads: list[list[int]]) -> int:
        parent = list(range(n + 1))

        def find(node: int) -> int:
            while parent[node] != node:
                parent[node] = parent[parent[node]]
                node = parent[node]
            return node

        for city_a, city_b, _ in roads:
            root_a, root_b = find(city_a), find(city_b)
            if root_a != root_b:
                parent[root_a] = root_b

        root = find(1)
        return min(dist for a, b, dist in roads if find(a) == root and find(b) == root)
```

## Complexity

| Time | Space |
| - | - |
| O(n + m \* alpha(m)) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.