Shortest Distance After Road Addition Queries I

Leetcode Problem:

• Shortest Distance After Road Addition Queries I

Summary

• Given an integer n and a 2D integer array queries, find the length of the shortest path from city 0 to city n-1 after processing the first i+1 queries.

Approach

• Use a queue to perform BFS from city 0 to city n-1
• For each query, add the new road to the queue and update the distance of each visited city.

Complexity

• O(n*Q) where n is the number of cities and Q is the number of queries

Solution Code:

struct _node{
    int n;
    int cnt;
};
class Solution {
public:
    vector adj[500];
    

    vector shortestDistanceAfterQueries(int n, vector>& queries) {
        vector ans;
        for(int i = 0 ; i < n-1; i++){
            adj[i].push_back(i+1);
        }
        for(int i = 0 ; i < queries.size(); i++){
            queue<_node> que;
            bool visited[500] = {false};
            int a = queries[i][0];
            int b = queries[i][1];
            adj[a].push_back(b);
            
            visited[0] = true;
            for(int j = 0 ; j < adj[0].size(); j++){
                que.push({adj[0][j], 1});
                visited[adj[0][j]] = true;
            }

            while(!que.empty()){
                _node nod = que.front();
                que.pop();
                if(nod.n == n-1){
                    ans.push_back(nod.cnt);
                    break;
                }
                for(int j = 0 ; j < adj[nod.n].size(); j++){
                    int next = adj[nod.n][j];
                    if(visited[next]) continue;
                    visited[next] = true;
                    que.push({next, nod.cnt + 1});
                }
            }
        }
        return ans;
    }
};