Minimum Score of a Path Between Two Cities
Problem
Given n cities numbered from 1 to n and a list of roads where each road connects two cities with a certain score, return the minimum score of any path between city 1 and city n. You may assume the graph is connected and the path can revisit cities and roads multiple times.
- 2 ≤ n ≤ 10⁵
- 1 ≤ roads.length ≤ 10⁵
- roads[i].length == 3
- 1 ≤ a_i, b_i ≤ n
- 1 ≤ score_i ≤ 10⁴
- There is at least one path between city 1 and city n
Example
n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]5The graph has edges with scores 9, 6, 5, and 7. The path from city 1 to city 4 can be direct with score 7, or via city 2 and 4 with edges 9 and 5. The minimum score along the path 1->2->4 is min(9,5) = 5, which is less than the direct edge 7. The algorithm uses DFS starting from city 1 to explore all reachable nodes, tracking the minimum edge score encountered. The critical moment is when the DFS visits edge (2,4) with score 5, updating the global minimum score to 5. Since the graph is connected, DFS visits all nodes reachable from city 1, ensuring the minimum edge score on any path to city n is found.
Approach
Straightforward Solution
A brute-force approach would enumerate all paths from city 1 to city n and compute the minimum edge score for each, then take the minimum among these. This is computationally infeasible due to exponential path counts.
Core Observation
The minimum score of a path between two cities is the smallest edge weight on any path connecting them. Since the graph is connected, all nodes reachable from city 1 can be explored, and the minimum edge score among all edges in the connected component containing city 1 is the answer.
Path to Optimal
Recognizing that the minimum edge score on any path from city 1 to city n must be at least the minimum edge in the connected component of city 1, the problem reduces to finding the minimum edge weight in that component. DFS or BFS can traverse the connected component efficiently, updating the minimum edge score encountered. This avoids enumerating all paths and achieves linear time complexity.
Optimal Approach
Build an adjacency list representation of the graph. Use DFS starting from city 1 to visit all reachable nodes. During traversal, track the minimum edge score encountered. Since the graph is connected, the DFS will reach city n, and the global minimum edge score found during traversal is the minimum score of any path between city 1 and city n.
Time
O(n + m)
Building the adjacency list takes O(m) time, where m is the number of roads. DFS visits each node and edge once, resulting in O(n + m) total time.
Space
O(n + m)
The adjacency list requires O(n + m) space. The recursion stack in DFS can go up to O(n) in the worst case. The visited set also uses O(n) space. This auxiliary space is necessary to track visited nodes and graph structure.
Pattern Spotlight
DFS (Graph Connectivity and State Propagation)
When the problem requires aggregating a property (like minimum edge weight) over all nodes reachable from a source in an undirected graph, a DFS traversal that propagates and updates a global state efficiently captures the solution without enumerating all paths.
Solution
| 1 | class Solution: |
| 2 | def minScore(self, n: int, roads: List[List[int]]) -> int: |
| 3 | graph = defaultdict(list) |
| 4 | |
| 5 | for a, b, w in roads: |
| 6 | graph[a].append((b, w)) |
| 7 | graph[b].append((a, w)) |
| 8 | |
| 9 | visited = set() |
| 10 | res = float("inf") |
| 11 | |
| 12 | def dfs(node): |
| 13 | nonlocal res |
| 14 | visited.add(node) |
| 15 | |
| 16 | for nei, w in graph[node]: |
| 17 | res = min(res, w) |
| 18 | if nei not in visited: |
| 19 | dfs(nei) |
| 20 | |
| 21 | dfs(1) |
| 22 | return res |
Step-by-Step Solution
Construct the Undirected Graph as an Adjacency List
| 3 | graph = defaultdict(list) |
| 5 | for a, b, w in roads: |
| 6 | graph[a].append((b, w)) |
| 7 | graph[b].append((a, w)) |
Objective
To represent the road network efficiently for traversal by building an adjacency list mapping each city to its neighbors and edge scores.
Key Insight
An adjacency list allows O(1) average-time access to neighbors of any node and is space-efficient for sparse graphs. Representing the graph as undirected requires adding each edge in both directions, ensuring traversal can proceed from any node to its connected neighbors.
Interview Quick-Check
Core Logic
Building the adjacency list with bidirectional edges ensures the graph accurately models the undirected road network.
Common Pitfalls & Bugs
Forgetting to add edges in both directions leads to incomplete traversal and incorrect results.
Initialize Visited Set and Result Variable
| 9 | visited = set() |
| 10 | res = float("inf") |
Objective
To prepare tracking structures for DFS traversal and to store the minimum edge score found during exploration.
Key Insight
The visited set prevents revisiting nodes and infinite recursion. Initializing the result to infinity ensures any edge score encountered will update it to a smaller value, correctly tracking the global minimum.
Interview Quick-Check
Core Logic
The visited set guarantees each node is processed once, preventing cycles and redundant work.
State & Boundaries
Initializing the result to infinity sets a correct baseline for minimum comparisons.
Traverse Graph with DFS to Update Minimum Edge Score
| 12 | def dfs(node): |
| 13 | nonlocal res |
| 14 | visited.add(node) |
| 16 | for nei, w in graph[node]: |
| 17 | res = min(res, w) |
| 18 | if nei not in visited: |
| 19 | dfs(nei) |
Objective
To recursively explore all nodes reachable from city 1, updating the global minimum edge score with each edge encountered.
Key Insight
DFS systematically visits every node and edge in the connected component. By updating the minimum edge score at each edge, the algorithm accumulates the smallest edge weight in the entire component. The use of a nonlocal variable allows the recursive calls to share and update this global state efficiently.
Interview Quick-Check
Core Logic
DFS explores all reachable nodes and edges, updating the global minimum edge score to reflect the smallest edge in the connected component.
State & Boundaries
The visited set prevents revisiting nodes, ensuring termination and correctness.
Common Pitfalls & Bugs
Failing to update the minimum edge score before recursive calls can miss smaller edges deeper in the graph.
Invoke DFS from City 1 and Return the Minimum Score
| 21 | dfs(1) |
| 22 | return res |
Objective
To start the DFS traversal from city 1 and return the minimum edge score found after full exploration.
Key Insight
Starting DFS at city 1 ensures the entire connected component containing city 1 is explored. Since the graph is connected, city n is guaranteed to be reachable, and the minimum edge score found during traversal is the answer. Returning the global minimum after traversal completes provides the final solution.
Interview Quick-Check
Core Logic
Starting DFS at city 1 ensures all nodes reachable from city 1, including city n, are visited.
State & Boundaries
Returning the global minimum after traversal completes gives the minimum score of any path from city 1 to city n.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
res = min(res, w)Update the global minimum edge score with the current edge weight.
This line is the core of the algorithm: it continuously tracks the smallest edge weight encountered during traversal, which directly determines the minimum score of any path between city 1 and city n.
nonlocal resDeclare res as nonlocal to update global minimum edge score.
Using nonlocal allows the recursive DFS calls to update the shared minimum edge score variable, maintaining state across recursion levels.
dfs(1)Start DFS traversal from city 1.
Initiating DFS at city 1 guarantees exploration of all nodes reachable from city 1, including city n, ensuring the minimum edge score is found.
graph = defaultdict(list)Initialize an adjacency list to represent the graph.
Using a defaultdict of lists provides an efficient and flexible structure to store neighbors and edge weights for each city, enabling quick lookups during traversal.
graph[a].append((b, w))Add neighbor and edge weight for city a.
Adding (b, w) to city a's adjacency list models the undirected edge from a to b with weight w.
graph[b].append((a, w))Add neighbor and edge weight for city b.
Adding (a, w) to city b's adjacency list completes the undirected edge representation, allowing traversal from b to a.
visited = set()Create a set to track visited cities during DFS.
The visited set prevents revisiting nodes, avoiding infinite recursion and redundant computations.
visited.add(node)Mark the current node as visited.
Adding the node to visited prevents revisiting it, ensuring the DFS terminates and does not process nodes multiple times.
if nei not in visited:Check if the neighbor has not been visited.
This condition prevents revisiting nodes, avoiding infinite recursion and redundant exploration.
dfs(nei)Recursively call DFS on the unvisited neighbor.
Recursing into unvisited neighbors ensures the entire connected component is explored, allowing the minimum edge score to be updated with all edges.
return resReturn the minimum edge score found after traversal.
Returning the global minimum edge score after DFS completes provides the final answer to the problem.
for a, b, w in roads:Iterate over each road to build the graph.
Processing each road allows the construction of the undirected graph by adding edges in both directions, ensuring connectivity representation.
res = float("inf")Initialize the result variable to infinity.
Setting the initial minimum edge score to infinity ensures any encountered edge weight will update it correctly to the smallest value.
def dfs(node):Define the DFS function to explore the graph.
Encapsulating the traversal logic in a recursive function allows systematic exploration of all reachable nodes and edges.
for nei, w in graph[node]:Iterate over neighbors and edge weights of the current node.
Exploring all adjacent nodes and their edge weights is essential to traverse the entire connected component and update the minimum edge score.
Test Your Understanding
Why does traversing the connected component of city 1 and tracking the minimum edge score guarantee the minimum score of any path to city n?
Because any path from city 1 to city n must lie entirely within the connected component of city 1, and the minimum edge score on any such path cannot be less than the smallest edge in that component. DFS visits all nodes and edges in this component, ensuring the global minimum edge score found is the minimum possible on any path.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Minimum Score of a Path Between Two Cities from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Minimum Score of a Path Between Two Cities drill