#2492

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

Minimum Score of a Path Between Two Cities

Find the minimum distance in a path connecting two cities using graph traversal strategies efficiently.

depth first search breadth first search union find graph

Problem Statement

You are given an integer n representing n cities numbered from 1 to n, along with a list of bidirectional roads, each described by [ai, bi, distancei]. Each road connects cities ai and bi with a specified distance distancei. The cities graph may not be fully connected, but there is always at least one path from city 1 to city n.

The score of a path is defined as the minimum distance of any road in that path. Your task is to find the minimum possible score for any path from city 1 to city n, ensuring all reachable roads are considered in the computation.

Examples

Example 1

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]

Output: 5

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

Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]

Output: 2

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.

Solution Approach

Depth-First Search

Perform DFS starting from city 1, recursively visiting each connected city while maintaining the minimum distance along the path. Track the global minimum encountered until city n is reached. DFS naturally explores deep paths but requires careful visited tracking to avoid cycles.

Breadth-First Search

Use BFS to traverse level by level from city 1, updating the minimum distance as each road is examined. BFS ensures shortest exploration sequences are processed first and avoids stack overflow issues that may arise in DFS for large graphs.

Union Find Optimization

Apply Union Find to identify connected components and merge nodes connected by roads. After all unions, compute the minimum edge in the component containing both cities 1 and n. This approach efficiently reduces repeated traversal when multiple queries or large graphs exist.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the chosen traversal: DFS or BFS is O(n + m) where n is the number of cities and m is the number of roads. Union Find can approach near-linear with path compression. Space complexity is O(n + m) for adjacency lists or Union Find structures.

What Interviewers Usually Probe

Are you considering all reachable paths to capture the true minimum distance?
Can you handle disconnected components without missing valid paths?
Have you thought about optimizing repeated minimum checks using Union Find?

Common Pitfalls or Variants

Common pitfalls

Failing to track the global minimum across all valid paths, leading to an incorrect score.
Not marking visited cities in DFS, which can create infinite loops or repeated paths.
Assuming the graph is fully connected and ignoring edge cases where only certain nodes are reachable.

Follow-up variants

Compute maximum score along any path instead of minimum, flipping the edge comparison logic.
Find minimum score between multiple city pairs, requiring repeated traversals or component precomputation.
Add weight constraints on roads, requiring filtered traversal and dynamic minimum updates.

FAQ

What is the best approach to solve Minimum Score of a Path Between Two Cities?

Use DFS or BFS to explore all reachable paths from city 1 while tracking the minimum road distance, or apply Union Find to consolidate components.

Can this problem be solved if the graph is disconnected?

Yes, but you must ensure there is a valid path from city 1 to city n; unreachable components are ignored.

How does Union Find help in computing the minimum score?

Union Find identifies connected components, allowing you to compute the minimum edge within the component containing both cities without redundant traversal.

Is BFS preferred over DFS in this problem?

BFS can avoid deep recursion issues present in DFS, especially for large graphs, but both approaches correctly track the minimum distance.

What are common mistakes when tracking the minimum score?

Common errors include not updating the global minimum correctly, revisiting nodes without proper checks, and assuming full graph connectivity.

terminal

Solution

Solution 1: DFS

According to the problem description, each edge can be passed multiple times, and it is guaranteed that node $1$ and node $n$ are in the same connected component. Therefore, the problem is actually looking for the smallest edge in the connected component where node $1$ is located. We can use DFS, start searching from node $1$, and find the smallest edge.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Solution 2: BFS

We can also use BFS to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#2493 divide nodes into the maximum number of groups #2368 reachable nodes with restrictions #2316 count unreachable pairs of nodes in an undirected graph