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
- 46 lines of C++ from the credited upstream file 3243.cpp.
- The implementation visibly relies on sequence storage, work queue.
- 4 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 public:3 vector<int> shortestDistanceAfterQueries(int n,4 vector<vector<int>>& queries) {5 vector<int> ans;6 vector<int> dist(n);7 vector<vector<int>> graph(n);8 9 iota(dist.begin(), dist.end(), 0);10 11 for (int i = 0; i < n - 1; ++i)12 graph[i].push_back(i + 1);13 14 for (const vector<int>& query : queries) {15 const int u = query[0];16 const int v = query[1];17 graph[u].push_back(v);18 if (dist[u] + 1 < dist[v]) {19 dist[v] = dist[u] + 1;20 bfs(graph, v, dist);21 }22 ans.push_back(dist[n - 1]);23 }24 25 return ans;26 }27 28 private:29 30 31 32 void bfs(const vector<vector<int>>& graph, int start, vector<int>& dist) {33 queue<int> q{{start}};34 while (!q.empty()) {35 const int u = q.front();36 q.pop();37 for (const int v : graph[u]) {38 if (dist[u] + 1 < dist[v]) {39 dist[v] = dist[u] + 1;40 q.push(v);41 }42 }43 }44 }45};46