3243. 新增道路查询后的最短距离 I
给你一个整数 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
的最短路径的长度。
思路:
一开始尝试利用求最短路的prim,floy的算法,发现均会超时,因为那些算法是不只是求从0到n的最短边,还至少包括从从0到其余边的,因此考虑其他做法。对于求最短路问题,比较常见的做法是利用bfs遍历,就是保存当前所有的边,然后每次新增加一个边后,就暴力bfs搜索从0到n-1的最小距离。一共需要搜索数组长度(q)次,每次搜索最多需要n+q的时间(就是把所有边全遍历一遍),最后近似500*500的时间,不会超时。
class Solution {
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {vector<int>ans;vector<vector<int>>g(n);for(int i=0;i<n-1;i++)g[i].push_back(i+1);auto bfs=[&](int i){vector<int>q={0};bool st[1000];memset(st,false,sizeof st);for(int step=1;;step++){ vector<int>nxt;for(auto x:q){ for(auto y:g[x]){if(y==n-1)return step;if(!st[y])nxt.push_back(y),st[y]=true;}}q=nxt;}};for(int i=0;i<queries.size();i++){int a=queries[i][0],b=queries[i][1];g[a].push_back(b);ans.push_back(bfs(i));}return ans;}
};
此外,本题还会发现,如果你对一条从a到b的边进行更新,所影响的只会是b之后的边,对于b之前的边不会有任何变化,也可以考用dp动态递归,每次加入新的边之后,如果这条边不会影响从0到b的最短距离,就不会影响b之后的最短距离,那就不会变化。反之,如果影响了从0到b的最短距离,就需要对b之后的边进行重新计算,具体计算方法是对于一个大于b的点q,暴力遍历所有0--q-1中到q的边,然后看是否可以更新0到q的最短距离。因为是要找以q为终点的距离,因此设置这个边的数组的时候可以保存以j为终点的边在dis[j]中。
class Solution {
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {vector<vector<int>>from(n);vector<int>f(n);for(int i=1;i<n;i++)f[i]=i;vector<int>ans;for(auto e:queries){int a=e[0],b=e[1];from[b].push_back(a);if(f[b]>f[a]+1){f[b]=f[a]+1;for(int i=b+1;i<n;i++){f[i]=min(f[i],f[i-1]+1);for(auto k:from[i])f[i]=min(f[i],f[k]+1);}}ans.push_back(f[n-1]);}return ans;}
};