Approach
Breadth-first search
For Shortest Distance After Road Addition Queries I, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 36 lines of Python from the credited upstream file 3243.py.
- The implementation visibly relies on sequence storage, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def shortestDistanceAfterQueries(3 self,4 n: int,5 queries: list[list[int]],6 ) -> list[int]:7 ans = []8 dist = list(range(n))9 graph = [[] for _ in range(n)]10 11 for i in range(n - 1):12 graph[i].append(i + 1)13 14 for u, v in queries:15 graph[u].append(v)16 if dist[u] + 1 < dist[v]:17 dist[v] = dist[u] + 118 self._bfs(graph, v, dist)19 ans.append(dist[n - 1])20 21 return ans22 23 def _bfs(self, graph: list[list[int]], start: int, dist: list[int]) -> None:24 """25 Performs a BFS to update the shortest distances from the given `start` node26 to all other reachable nodes in the graph. It updates the `dist` vector27 with the new shortest distances.28 """29 q = collections.deque([start])30 while q:31 u = q.popleft()32 for v in graph[u]:33 if dist[u] + 1 < dist[v]:34 dist[v] = dist[u] + 135 q.append(v)36