Get started

Minimum Score of a Path Between Two Cities — Medium Problem & Solution

n cities numbered 1 … n are joined by bidirectional roads; roads[i] = [a, b, distance]. The score of a path is the minimum distance among the roads it uses.

Problem statement

n cities numbered 1 … n are joined by bidirectional roads; roads[i] = [a, b, distance].

The score of a path is the minimum distance among the roads it uses. A path may revisit cities and reuse roads, and need not be the shortest. Return the minimum possible score of any path from city 1 to city n. City n is reachable from city 1.

Example 1

Input: roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]], n = 4
Output: 5
Explanation: Walk 1 → 2 → 4 → 2 → 4: the road of length 5 is on the path.

Example 2

Input: roads = [[1,2,2],[1,3,4],[3,4,7]], n = 4
Output: 2
Explanation: Detour over the road of length 2 and come back.

Example 3

Input: roads = [[1,2,3]], n = 2
Output: 3

Constraints

  • 2 <= n <= 10^5
  • 1 <= roads.length <= 10^5
  • roads[i].length == 3
  • 1 <= a, b <= n
  • a != b
  • 1 <= distance <= 10^4
  • There are no repeated edges.
  • City n is reachable from city 1.

How to solve Minimum Score of a Path Between Two Cities

Because a path can revisit cities and reuse roads, it can detour to any road in city 1's connected component and come back. So the answer is simply the minimum weight among the component's roads.

Approach

  1. Union the endpoints of every road.
  2. Find the component root of city 1 — city n is in it by assumption.
  3. Scan the roads and take the minimum weight among those inside that component.

Why it works

This is why no shortest-path algorithm appears: the usual trade-off between path length and edge weights vanishes once revisiting is free. Detouring along the component's lightest road, then walking on to city n, gives a path whose minimum is that weight — and no path can beat it, since every road it uses lies in the component.

Complexity

  • Time — O(n + m · α(n))
  • Space — O(n)

Pitfalls

  • Dijkstra's algorithm answers a different question and gives the wrong result here.
  • Roads outside city 1's component must be ignored, however light.
  • Cities are numbered from 1, so size the union-find arrays accordingly.

Reference solution

Python

from typing import List

def minScore(n: int, roads: List[List[int]]) -> int:
    parent = list(range(n + 1))

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

    for a, b, _ in roads:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
    root = find(1)
    return min(d for a, _, d in roads if find(a) == root)

JavaScript

var minScore = function(n, roads) {
    var i;
    var parent = [];
    for (i = 0; i <= n; i++) parent.push(i);
    var find = function(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    for (i = 0; i < roads.length; i++) {
        var a = find(roads[i][0]), b = find(roads[i][1]);
        if (a !== b) parent[b] = a;
    }
    var root = find(1);
    var best = 1000000000;
    for (i = 0; i < roads.length; i++) {
        if (find(roads[i][0]) !== root) continue;
        if (roads[i][2] < best) best = roads[i][2];
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 65 breadth-first search problems · the whole catalogue