⚡Flashcard Drill➔
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

  1. Cities 1 and n lie in the same connected component, and the score of a path is its smallest edge.
  2. 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.
  3. So a single DFS/BFS from city 1, taking the minimum edge weight encountered, suffices.
  4. 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 seen set: 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems