本文主要是介绍4196.最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个 n 个点 m 条边的的无向图。点的编号从 1 到 n。图中可能包含重边和自环。请你找到并输出一条从点 1 到点 n 的最短路径。
输入格式
第一行包含两个整数 n,m。接下来 m 行，每行包含三个整数 a,b,w，表示点 a 和点 b 之间存在一条无向边，边长为 w.
输出格式
如果最短路径不存在，则输出 −1。否则，在一行内输出从点 1 到点 n
的最短路径中依次包含的点的编号，各点编号之间用空格隔开。如果答案不唯一，输出任意合理方案均可。
数据范围
前六个测试点满足 2≤n≤10，1≤m≤10。所有测试点满足
2≤n≤105，1≤m≤105，
1≤a,b≤n，
1≤w≤106。
本题不卡spfa算法。
输入样例：
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
输出样例：
1 4 3 5
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],w[M],idx;
int q[N];
long long dist[N];
int n,m;
bool st[N];
int pre[N];
int path[N];
void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa()
{int hh=0,tt=0;memset(dist,0x3f,sizeof dist);memset(pre,-1,sizeof pre);dist[1]=0;st[1]=true;q[hh++]=1;while(tt<hh){int t=q[tt++];if(tt==N) hh=0;st[t]=false;for(int i=h[t];~i;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];pre[j]=t;if(!st[j]){q[hh++]=j;if(hh==N) tt=0;st[j]=true;}}}}
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);while (m -- ){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}spfa();if(pre[n]==-1) cout<<"-1";else{int cnt=0;for(int i=n;~i;i=pre[i]) path[cnt++]=i;for(int i=cnt-1;i>=0;i--) cout<<path[i]<<" ";}return 0;
}
这篇关于4196.最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
