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.
An undirected road network contains n cities numbered from 1 through n. Each road is described as [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 a road more than once. Return the minimum score achievable by any route that starts at city 1 and ends at city n. At least one route from city 1 to city n always exists.
Example 1:
n = 4, roads = [[1, 2, 9], [2, 3, 6], [3, 4, 7], [1, 4, 10]]
returns 6
The route 1 -> 2 -> 3 -> 4 uses roads with distances 9, 6, and 7, so its score is 6; no route achieves a smaller score.
Example 2:
n = 3, roads = [[1, 2, 5], [2, 3, 5], [1, 3, 8]]
returns 5
Roads (1, 2) and (2, 3) both have distance 5, so the route 1 -> 2 -> 3 scores 5.
Output semantics: return a single integer, the minimum achievable score. Multiple roads may connect the same pair of cities, and roads may be listed in any order. Every distance is between 1 and 1_000_000_000, so the answer always fits in a 32-bit signed integer.
Constraints
- 2 <= n <= 100_000
- 1 <= len(roads) <= 100_000
- roads[i] = [u, v, distance] with 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
Input: (4, [[1, 2, 9], [2, 3, 6], [3, 4, 7], [1, 4, 10]])
Expected Output: 6
Explanation: Worked example 1 from the prompt: the route 1 -> 2 -> 3 -> 4 uses distances 9, 6, and 7, so its score is 6, and no route does better.
Input: (3, [[1, 2, 5], [2, 3, 5], [1, 3, 8]])
Expected Output: 5
Explanation: Worked example 2 from the prompt: two roads tie at distance 5 and the route 1 -> 2 -> 3 achieves that score.
Hints
- A route may reuse cities and roads, so you are not limited to simple paths. Think about which roads a route from city 1 could ever touch.
- If a road is reachable from city 1, you can travel to it, cross it, and backtrack; the guaranteed route to city n lets you finish afterward.
- Build the connected component containing city 1 with BFS, DFS, or union-find, then aggregate over the roads inside it.