当前位置:网站首页>牛客:飞行路线(分层图+最短路)

牛客:飞行路线(分层图+最短路)

2022-06-25 06:43:00 mfy的1号小迷弟

牛客:飞行路线(分层图+最短路)

题意:

一个带边权的图,求从s到t的最短距离,可以忽略k条边的权值。

2 < = n < = 10000 , 1 < = m < = 50000 , 0 < = k < = 10 2<=n<=10000,1<=m<=50000,0<=k<=10 2<=n<=10000,1<=m<=50000,0<=k<=10
思路:

因为k很小,可以想 到分层图,把原图看成k层,每层完全一样,再建新边把每层连起来,对于第一层的从x到y,把x每层对应的点和下一层的y连一条权值为0的边,把y每层对应的点和下一层的x连一条权值为0的边。这样从某层的x到下一层的y就表示用了一次k

再跑最短路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef pair<int,int>pii;
const int maxn=3e6+5;
int s,n,m,t,k,d,dis[maxn],vis[maxn],head[maxn],w[maxn],to[maxn],nex[maxn];
void add(int x,int y,int z){
    
	nex[++d]=head[x];
	to[d]=y;
	w[d]=z;
	head[x]=d;
}
void dij(){
    
	memset(dis,INF,sizeof(dis));
	dis[s]=0;
	priority_queue<pii,vector<pii>,greater<pii>>p;
	p.push({
    0,s});
	while(!p.empty()){
    
		int x=p.top().second;
		p.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=nex[i]){
    
			int y=to[i];
			if(dis[y]>dis[x]+w[i]){
    
				dis[y]=dis[x]+w[i];
				p.push({
    dis[y],y});
			}
		}
	}
}
int main(){
    
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
	for(int i=1,x,y,z;i<=m;i++){
    
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
		for(int j=1;j<=k;j++){
    
			add(x+j*n,y+j*n,z);
			add(y+j*n,x+j*n,z);
			add(x+(j-1)*n,y+j*n,0);
			add(y+(j-1)*n,x+j*n,0);
		}
	}
	dij();
	int ans=INF;
	for(int i=0;i<=k;i++){
    
		ans=min(ans,dis[i*n+t]);
	}
	printf("%d\n",ans);
}
原网站

版权声明
本文为[mfy的1号小迷弟]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_45722843/article/details/118786195