⚡Flashcard Drill➔
NeetCode #600LC-3243MediumGraphs
← Back to All Problems

#600 · #3243 · Shortest Distance After Road Addition Queries I(新增道路查询后的最短距离 I)

📌 Problem Statement & Constraints

There are n cities numbered 0..n-1 with a directed road from i to i+1 for each i. For each query [u, v], add a road u -> v and return the shortest path length from 0 to n-1. Constraints: 1 <= n <= 500, 1 <= queries.length <= 500, 0 <= u < v < n.

💡 Core Algorithmic Approaches

  1. Roads only go forward, so a BFS from 0 gives the shortest distance.
  2. After each query, re-run the BFS over the updated adjacency list.
  3. With n, q <= 500 this is at most 500 * (500 + 500) operations -- comfortably fast.
  4. For much larger inputs, a more clever incremental structure would be needed.

💻 Benchmark Python3 Implementation

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        from collections import deque
        adj = [[] for _ in range(n)]
        for i in range(n - 1):
            adj[i].append(i + 1)           # the initial chain

        def bfs() -> int:
            dist = [-1] * n
            dist[0] = 0
            q = deque([0])
            while q:
                node = q.popleft()
                if node == n - 1:
                    return dist[node]
                for nxt in adj[node]:
                    if dist[nxt] == -1:
                        dist[nxt] = dist[node] + 1
                        q.append(nxt)
            return dist[n - 1]

        res = []
        for u, v in queries:
            adj[u].append(v)               # add the new road
            res.append(bfs())
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(q * (V + E)): one BFS per query.
💾 Space Complexity
O(V + E) for the adjacency list.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming the graph stays a simple chain: the added roads create shortcuts.
  • Forgetting the initial chain: without it, only the added roads exist.
  • Using a DFS: it does not guarantee the shortest path.
  • Caching the previous answer: a new road can only shorten the distance, but the recomputation is still needed to know by how much.
⚡
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