方法一：广度优先搜索
前面说到，深度优先搜索是一条路径走到底再回溯。而广度优先搜索是先探索深度相同的所有节点，再拓展深度。如果在树中，就是层序遍历。
此题中，只需从0开始搜索与它直接相连的节点，更新距离。再进一步搜索与这些节点直接相连的节点，继续更新距离即可。
class Solution
{
public:int bfs(int n, const vector<vector<int>>& graph){vector<int>dis(n, -1);//dis[i]表示节点0到节点i的最短距离queue<int>que;que.push(0);dis[0] = 0;while (!que.empty()){int x = que.front();que.pop();for (int t : graph[x]){if (dis[t] >= 0)//由于从0开始，所以如果dis[t]已经非负，意味着已经有最短路径了//举个例子：先连接0与3，再连接0与2。对与2直接相连的节点进行bfs时，会发现dis[3]已经非负了{continue;}que.push(t);dis[t] = dis[x] + 1;}}return dis[n - 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>res;for (auto& q : queries){graph[q[0]].push_back(q[1]);res.push_back(bfs(n, graph));}return res;}
};
方法二：动态规划
class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {vector<vector<int>>prev(n);//prev[i]中存储的节点都是可以直接到达节点i的vector<int>dis(n);//节点0到节点i的距离for (int i = 1; i < n; i++){prev[i].push_back(i - 1);dis[i] = i;}vector<int>ans;for(auto&q:queries){prev[q[1]].push_back(q[0]);for(int v=q[1];v<n;v++)//添加一条q[0]->q[1]的路径后，只有q[1]及其后面的节点到节点0的距离会改变{for(int u:prev[v]){dis[v]=min(dis[v],dis[u]+1);}}ans.push_back(dis[n-1]);}return ans;}
};模拟一下就很清晰了。假设是0->1->2->3->4->5.现在我们新建一条路2->4，那么从4开始往后的节点到节点0的最短路长度就会改变。从4开始：这时与4直接相连的节点有3，2.开始遍历这两个节点：当u=3，dis[3]+1=dis[4]，不改变；当u=2，dis[2]+1=3<dis[4]，更新dis[4]。接着到5：由于改变了dis[4]，所以dis[5]也会发生改变。也就是说，这种改变是从前往后推的。
