3243. Shortest Distance After Road Addition Queries I

You are given an integer n and a 2D integer array queries.

There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1.

queries[i] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. After each query, you need to find the length of the shortest path from city 0 to city n - 1.

Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

c++

class Solution {
    int helper(vector<vector<int>>& adj) {
        queue<int> q;
        vector<int> vis(adj.size());
        auto push = [&](int u) {
            if(!vis[u]) {
                vis[u] = true;
                q.push(u);
            }
        };
        int res = 0;
        push(0);
        while(!vis.back()) {
            int qsz = q.size();
            while(qsz--) {
                auto u = q.front(); q.pop();
                for(auto& v : adj[u]) push(v);
            }
            res++;
        }
        return res;
    }
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> adj(n);
        for(int i = 0; i < n - 1; i++) {
            adj[i].push_back(i+1);
        }
        vector<int> res;
        for(auto& q : queries) {
            adj[q[0]].push_back(q[1]);
            res.push_back(helper(adj));
        }
        return res;
    }
};