1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution{
private:
    int bfs(int n, vector<vector<int>>&neighbor)
    {
        vector<int> dist(n,-1); // 定义每个点到起点的距离
        queue<int> q;           // 用于bfs遍历的队列
        q.push(0);              // 将起点加入队列
        dist[0]=0;              // 0~0 距离为0
        while(!q.empty())
        {
            int x = q.front(); // 取出当前起点
            q.pop();
            for(auto &y: neighbor[x])  // 遍历下一个节点
            {
                if(dist[y]!=-1)
                    continue;       // 如果已经访问过了，直接跳过
                q.push(y);
                dist[y] = dist[x]+1; // 计算0到x的距离，+1
            }
        }
        return dist[n-1];
    }
public:
    vector<int> shortestDistanceAfterQueries(int n,
                                             vector<vector<int>>& queries) {
        vector<vector<int>> graph(n);   // 定义图
        vector<int> result;             // 定义结果集
        for (int i = 0; i < n - 1; i++) {
            graph[i].emplace_back(i+1); // 建图
        }
        for (auto& query : queries) {
            graph[query[0]].emplace_back(query[1]); // 插入边
            result.emplace_back(bfs(n, graph));         // 计算图更新后的结果
        }
        return result;
    }
};