最短路:多层图(已完)
2025-06-14 21:56:32
发布于：上海
多层图可以运用在最短路的一些问题上.是最短路的一种题型.本篇从题目入手进行分析.
前置只是:邻接表,最短路算法(最好使用Dijkstra)
多层图作为最短路算法的一种题型,主要操作集中在输入上.(输入时,在vector中建多层图)
P4568 [JLOI2011] 飞行路线 (洛谷)
大致题意不太想分析...
本题重点在于:可以免费在最多k种航线上搭乘飞机
多层图在此处的体现是建立k+1层图,并进行最短路(dij).
*此处的k是上文提到的"免费的k种航线"
这里k+1层图分为两个部分:
1.第一层图:题目给出的数据本身就是一层图,以样例为例:
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
(这里点2到点3之间的距离直接取最小值)
2.剩下的k层图:
(这里的k为1,所以本来应该只有1层图,因后续讲解需要将其与第一层图话在一起)
多层图,顾名思义,有很多层,在这道题目中,总共需要建k+1层,而第二部分中的k层,题目中没有直接给出,而是需要自己建的.
这里建图的代码是这样的:
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
//k+1层图
for(int j=0;j<=k;j++){
//每一层的结构其实很像.(建立本层)
v[a+j*n].push_back({b+j*n,c});
v[b+j*n].push_back({a+j*n,c});
if(j!=k){
//建立本层和下层的联系,其权值全部为0.
v[a+j*n].push_back({b+(j+1)*n,0});
v[b+j*n].push_back({a+(j+1)*n,0});
}
}
}
建图有两个部分:
1.建立本层(第j层)
2.建立本层和下层的练习(第j层和第j层的联系)
因为输入是一条边一条边输入的,所以这两个部分在每次输入一条边时,都需要进行.
而且,建图过程中有一些需要注意的
(配合代码一起理解)
比如说,建立本层时的代码:
v[a+j*n].push_back({b+j*n,c});
它的在邻接表中的下标 : a + j * n
其 j * n 的 j 就是第 j 层的意思(这边的层数的范围是是 0 - k )
然后这边就涉及了另一个点:终点到底是哪个点?
以此图为例:
这里的终点是由两个的:点4和点9
可以发现,虽然顶点编号不一,但是它们确实都是终点.
那么,最后输出终点的代码是:
for(int i=0;i<=k;i++){
answer=min(answer,dis[t+i*n]);
}
cout<<answer;
可以配合上文给出的图片一起理解建图代码.
再比如说,这边建立本层和下层的连接的代码:
v[a+j*n].push_back({b+(j+1)*n,0});
这个连接边的权值为0(代表了免费航线)
然后,解释一下为什么运用多层图后,可以保证,从起点到终点,只会经过k条权值为0的边.
可以是用反证法,即说明:运用多层图后,从起点到终点,可能会经过大于k条权值为0的边(来达成"最短路")
但是,也可以轻易地发现:如果第一层图到第二层图(经过一条权值为0的边),再上去,只会增加路径长度.
而这条法则使用每一层.只要往下一层,想再次返回,是没有利益的.
所以说,就算是有可能经过k条权值等于0的边,最短路算法也不会选择这种可能.
这道题目比较需要思考的就是输入时的预处理和输出.
中间部分就是普通的Dijkstra算法.
代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int s,t;
const int N=1e4+10;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[12*N];
long long dis[12*N];
bool vis[12*N];
priority_queue<Node>q;
void dij(){
for(int i=0;i<=n*11;i++){
dis[i]=1e9;
}
dis[s]=0;
q.push({s,0});
while(!q.empty()){
Node sum=q.top();
q.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
q.push({to,dis[to]});
}
}
}
}
int main(){
cin>>n>>m>>k;
cin>>s>>t;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
for(int j=0;j<=k;j++){
v[a+j*n].push_back({b+j*n,c});
v[b+j*n].push_back({a+j*n,c});
if(j!=k){
v[a+j*n].push_back({b+(j+1)*n,0});
v[b+j*n].push_back({a+(j+1)*n,0});
}
}
//本层和下层建立联系
}
dij();
long long answer=INT_MAX;
for(int i=0;i<=k;i++){
answer=min(answer,dis[t+i*n]);
}
cout<<answer;
return 0;
}
这里空空如也
有帮助，赞一个