Dijkstra多层图
2025-06-14 15:28:48
发布于：上海
0阅读
0回复
0点赞
整体思路：
顾名思义，在原Dijkstra模板上，要建立多层图，再将每个图之间可抵达的点建立联系。
例题：洛谷P4568：飞行路线
描述：
在Dijkstra的模板基础上加入了k次免费的通行。
思路：
建立k+1层图(原来的一层图加上k层图)，在原基础的n个点上，在之后新的图上的每个点都在原1-n的点上依次加上n，就可以得到第二个图，以此类推，再建立k个图。然后就是Dijkstra了，但是最后答案的时候要筛选出 t -> t + k * n中最小的那一个(t为终点)。
核心代码如下：
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
for(int j=0;j<=k;j++){
//建图
v[x + j * n].push_back({y + j * n,z});
v[y + j * n].push_back({x + j * n,z});
//层与层之间建立联系
if( j != k){
v[x + j * n].push_back({ y + (j + 1) * n , 0});
v[y + j * n].push_back({ x + (j + 1) * n , 0});
}
}
}
//答案
int ans = 1e9;
for(int i=0;i<=k;i++)
ans = min( ans , dis[t + i * n]);
cout<<ans;
这里空空如也
有帮助，赞一个