题目：
给你一个整数 n 和一个二维整数数组 queries。有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。
示例 1：
输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：
新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。
新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。
新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。
示例 2：
输入： n = 4, queries = [[0, 3], [0, 2]]
输出： [1, 1]
解释：
新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。
提示：
3 <= n <= 5001 <= queries.length <= 500queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]- 查询中没有重复的道路。
思路：
由于图在每个查询都在变化，那么从 0 到 n - 1 的最短路径可能会一直改变，所以需要多次查询
每次查询通过 bfs 查询最短路径即可
代码：
class Solution {
public:
int bfs(vector<vector<int>>& graph, int n) {
vector<bool> visit(n, false);
queue<pair<int, int>> que;
que.push(make_pair(0, 0));
visit[0] = true;
while (!que.empty()) {
auto top = que.front();
if (top.first == n - 1) return top.second;
que.pop();
for (int i = 0; i < graph[top.first].size(); i++) {
if (!visit[graph[top.first][i]]) {
que.push(make_pair(graph[top.first][i], top.second + 1));
visit[graph[top.first][i]] = true;
}
}
}
return -1;
}
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
vector<vector<int>> graph(n);
for (int i = 0; i < n - 1; i++) {
graph[i].push_back(i + 1);
}
vector<int> ans(queries.size());
for (int i = 0; i < queries.size(); i++) {
graph[queries[i][0]].push_back(queries[i][1]);
ans[i] = bfs(graph, n);
}
return ans;
}
};