NeetCode #589LC-2492MediumGraphs
← Back to All Problems#589 · #2492 · Minimum Score of a Path Between Two Cities(两个城市间路径的最小分数)
📌 Problem Statement & Constraints
You are given
n cities and roads[i] = [a, b, distance]. A path's score is its minimum road distance. Return the minimum possible score over all paths between city 1 and city n. Constraints: 2 <= n <= 10^5, n - 1 <= roads.length <= 10^5, 1 <= distance <= 10^4; the graph is connected.💡 Core Algorithmic Approaches
- Cities 1 and
nlie in the same connected component, and the score of a path is its smallest edge. - Any edge inside that component can be included in some path from 1 to
n(by detouring), so the answer is simply the minimum edge weight in the component. - So a single DFS/BFS from city 1, taking the minimum edge weight encountered, suffices.
- No shortest-path algorithm is needed.
💻 Benchmark Python3 Implementation
class Solution:
def minScore(self, n: int, roads: List[List[int]]) -> int:
from collections import defaultdict
g = defaultdict(list)
for a, b, d in roads:
g[a].append((b, d))
g[b].append((a, d))
seen = {1}
stack = [1]
best = float("inf")
while stack:
node = stack.pop()
for nxt, d in g[node]:
best = min(best, d) # any edge in the component is usable
if nxt not in seen:
seen.add(nxt)
stack.append(nxt)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): one traversal.
💾 Space Complexity
O(V + E) for the graph.
⚠️ Interview Pitfalls & Follow-ups
- Running Dijkstra or a max-min path search: unnecessary -- the detour argument makes it a plain minimum.
- Only considering edges on a shortest path: any edge in the component can be visited.
- Forgetting the
seenset: the traversal would loop. - Assuming the graph is a tree: it may have cycles, which is exactly why detours are possible.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.