Find the Minimum Edge Score on a Path Between Two Cities
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Find the Minimum Edge Score on a Path Between Two Cities
An undirected road network contains `n` cities numbered from `1` through `n`. Each road is represented by `[u, v, distance]` and can be traveled in either direction. The **score** of a route is the smallest road distance used anywhere on that route.
A route may visit a city or road more than once. Return the minimum score achievable by any route that starts at city `1` and ends at city `n`.
## Function Signature
```python
def minimum_path_score(n: int, roads: list[list[int]]) -> int:
...
```
## Input and Output
- `n` is the number of cities.
- Every element of `roads` is `[u, v, distance]`.
- Return one integer: the minimum achievable route score from city `1` to city `n`.
## Constraints
- `2 <= n <= 100_000`
- `1 <= len(roads) <= 100_000`
- `1 <= u, v <= n` and `u != v`
- `1 <= distance <= 1_000_000_000`
- At least one route exists from city `1` to city `n`.
## Examples
```text
Input: n = 4, roads = [[1, 2, 9], [2, 3, 6], [3, 4, 7], [1, 4, 10]]
Output: 6
```
```text
Input: n = 3, roads = [[1, 2, 5], [2, 3, 5], [1, 3, 8]]
Output: 5
```
Quick Answer: Find the minimum edge score achievable on a route between two cities in a large undirected road network, where revisiting cities and roads is allowed. The problem tests graph-component reasoning, traversal at scale, careful interpretation of a path score, and resistance to applying a standard shortest-path metric blindly.