登录
← 返回首页 | 代码片段 › 3 图论 › 3.1 最短路 › 最短路 / 搜索
JSON MD

3.1 最短路

dijkstra (信使) n^2
27 行
CPP JSON
【dijkstra (信使)(n^2)】 Dijkstra 最短路算法模板,适用于非负权图。 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 26 行 CPP
#include<bits/stdc++.h>
using namespace std;
int i,j,ans,a,b,z,n,m,pan[110],w,mi,f[110][110],dis[110];
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            f[i][j]=0xfffffff;
    for(i=1;i<=n;i++)dis[i]=0xfffffff;
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&z);
        f[a][b]=f[b][a]=z;
    }
    for(i=1;i<=n;i++)dis[i]=f[1][i];
    dis[1]=0;pan[1]=1;
    for(i=1;i<=n;i++){
        w=0;mi=0xfffffff;
        for(j=1;j<=n;j++)if(!pan[j]&&dis[j]<mi)mi=dis[w=j];
        if(!w)break;pan[w]=1;
        for(j=1;j<=n;j++)dis[j]=min(dis[j],dis[w]+f[w][j]);
    }
    for(i=1;i<=n;i++)ans=max(ans,dis[i]);
    if(ans==0xfffffff)printf("-1");
    else printf("%d",ans);
    return 0;
}
最小环 (Sightseeing Trip) Floyed
44 行
CPP JSON
【最小环 (Sightseeing Trip)(Floyed)】 最短路算法模板,求解图中两点间的最短路径。 核心函数: void in(Re &x) — 核心算法函数 void get(Re i,Re j) — 获取值 关键配置: N=103,inf=1e8 复杂度:时间复杂度取决于具体算法 说明:freopen("123.txt","r",stdin); 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
using namespace std;
const int N=103,inf=1e8;
int n,m,x,y,z,ans,Ans[N],a[N][N],g[N][N],dis[N][N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void get(Re i,Re j){
	Re k=g[i][j];if(!k)return;
	get(i,k),Ans[++Ans[0]]=k,get(k,j);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=n;++j)
			dis[i][j]=a[i][j]=inf;
	for(Re i=1;i<=n;++i)dis[i][i]=a[i][i]=0;
	while(m--)in(x),in(y),in(z),dis[x][y]=dis[y][x]=a[x][y]=a[y][x]=min(a[x][y],z);
	ans=inf;
	for(Re k=1;k<=n;++k){
		for(Re i=1;i<k;++i)
			for(Re j=i+1,tmp;j<k;++j)	
				if((tmp=dis[i][j]+a[j][k]+a[k][i])<ans){
					ans=tmp,Ans[0]=0;
					Ans[++Ans[0]]=i;
					get(i,j);
					Ans[++Ans[0]]=j;
					Ans[++Ans[0]]=k;
				}
		for(Re i=1;i<=n;++i)
			for(Re j=1,tmp;j<=n;++j)
				if((tmp=dis[i][k]+dis[k][j])<dis[i][j])	
					dis[i][j]=tmp,g[i][j]=k;
	}
	if(ans==inf)puts("No solution.");
	else for(Re i=1;i<=Ans[0];++i)printf("%d ",Ans[i]); 
}
最短路 dijkstra
38 行
CPP JSON
【最短路(dijkstra)】 Dijkstra 最短路算法模板,适用于非负权图。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void dijkstra(Re st) — Dijkstra最短路 核心结构体:QAQ, QWQ 关键配置: N=1e5+5,M=1e5+5,inf=2e9 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 37 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e5+5,M=1e5+5,inf=2e9;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
struct QWQ{int x,d;inline bool operator<(QWQ O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void dijkstra(Re st){
	for(Re i=0;i<=n;++i)dis[i]=inf;
	dis[st]=0,Q.push((QWQ){st,0});
	while(!Q.empty()){
		x=Q.top().x,Q.pop();
		if(pan[x])continue;
		pan[x]=1;
		for(Re i=head[x];i;i=a[i].next)
			if(dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w;
				Q.push((QWQ){to,dis[to]});
			}
	}
}
int main(){
	in(n),in(m),in(st);
	while(m--)in(x),in(y),in(z),add(x,y,z);
	dijkstra(st);
	for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}
最短路 SPFA
36 行
CPP JSON
【最短路(SPFA)】 SPFA 最短路算法模板,队列优化的 Bellman-Ford。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re y,Re z) — 加法更新 void SPFA(Re st) — SPFA最短路 核心结构体:QAQ 关键配置: N=1e4+5,M=5e5+5,inf=2147483647 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 35 行 CPP
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=1e4+5,M=5e5+5,inf=2147483647;
int x,y,z,n,m,o,to,st,dis[N],pan[N],head[N];
struct QAQ{int w,to,next;}a[M<<1];
queue<int>Q;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void add(Re x,Re y,Re z){a[++o].to=y,a[o].w=z,a[o].next=head[x],head[x]=o;}
inline void SPFA(Re st){
	for(Re i=0;i<=n;++i)dis[i]=inf;
	dis[st]=0,pan[st]=1,Q.push(st);
	while(!Q.empty()){
		x=Q.front(),Q.pop();
		pan[x]=0;
		for(Re i=head[x];i;i=a[i].next)
			if(dis[to=a[i].to]>dis[x]+a[i].w){
				dis[to]=dis[x]+a[i].w;
				if(!pan[to])pan[to]=1,Q.push(to);
			}
	}
}
int main(){
	in(n),in(m),in(st);
	while(m--)in(x),in(y),in(z),add(x,y,z);
	SPFA(st);
	for(Re i=1;i<=n;++i)printf("%d ",dis[i]);
}
次短路 SPFA
44 行
CPP JSON
【次短路(SPFA)】 SPFA 最短路算法模板,队列优化的 Bellman-Ford。 核心函数: void add(Re x,Re y,Re z) — 加法更新 void in(Re &x) — 核心算法函数 void SPFA(Re st) — SPFA最短路 核心结构体:QAQ 关键配置: N=5003,M=1e5+3,inf=1e9 复杂度:时间复杂度取决于具体算法 适用场景:图中最短路径计算、网格寻路、分层图最短路
C++ 43 行 CPP
#include<algorithm>
#include<cstdio>
#include<queue>
#define Re register int
using namespace std;
const int N=5003,M=1e5+3,inf=1e9;
int n,m,x,y,z,o,pan[N],head[N],dis[N][2];
struct QAQ{int w,to,next;}a[M<<1];queue<int>Q;
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    Re fu=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=fu?-x:x;
}
inline void SPFA(Re st){
    for(Re i=0;i<=n;++i)dis[i][0]=dis[i][1]=inf;
    dis[st][0]=0,pan[st]=1,Q.push(st);
    while(!Q.empty()){
        Re x=Q.front();Q.pop();pan[x]=0;
        for(Re i=head[x],to,tmp;i;i=a[i].next){
            if(dis[to=a[i].to][0]>(tmp=dis[x][0]+a[i].w)){
                dis[to][1]=dis[to][0];
                dis[to][0]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
            if(dis[to][1]>(tmp=dis[x][0]+a[i].w)&&tmp>dis[to][0]){
                dis[to][1]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
            if(dis[to][1]>(tmp=dis[x][1]+a[i].w)){
                dis[to][1]=tmp;
                if(!pan[to])pan[to]=1,Q.push(to);
            }
        }
    }
}
int main(){
    in(n),in(m);
    while(m--)in(x),in(y),in(z),add(x,y,z),add(y,x,z);
    SPFA(1);
    printf("%d\n",dis[n][1]);
}
已复制