题目链接：https://www.luogu.com.cn/problem/CF20C 本题是最短路模板题 spfa的做法
//spfa #include<iostream> #include<stack> #include<queue> #include<cstring> using namespace std; stack<int>st; struct edge{ long long n,o,v; }e[200005]; long long w,last[200005],dist[200005],flag[200005],n,m; long long yes,pre[200005]; inline void add(long long x,long long y,long long z){ w++; e[w].n=last[x]; last[x]=w; e[w].o=y; e[w].v=z; } void spfa(long long s){ long long x,w1,y; memset(dist,42,sizeof(dist)); dist[s]=0; memset(flag,0,sizeof(flag)); flag[s]=1; queue<long long>q; q.push(s); while(q.size()){ x=q.front(); if(x==n)yes=1; q.pop(); flag[x]=0; for(long long w1=last[x];w1;w1=e[w1].n){ y=e[w1].o; if(dist[x]+e[w1].v<dist[y]){ dist[y]=dist[x]+e[w1].v; pre[y]=x; if(flag[y]==0){ flag[y]=1; q.push(y); } } } } } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); cin>>n>>m; long long x,y,v; for(long long i=1;i<=m;i++){ scanf("%lld%lld%lld",&x,&y,&v); add(x,y,v); add(y,x,v); } spfa(1); if(yes==0){ cout<<-1<<endl; return 0; } int now=n; while(now){ st.push(now); now=pre[now]; } while(st.size()>0){ cout<<st.top()<<" "; st.pop(); } return 0; }堆优化dijkstra的做法
#include<iostream> #include<cstring> #include<queue> #include<stack> using namespace std; #define N 110000 #define M 210000 long long last[N],yes,pre[N],dist[N],x,y,z,n,m,w,flag[N]; struct edge{ long long n,o,l; }e[M]; struct arr{ long long di,id; }; stack<long long>st; priority_queue<arr,vector<arr>,less<arr> >q; bool operator <(arr a,arr b){//结构体小根堆 return a.di>b.di; } void add(long long x,long long y,long long z){ w++;e[w].n=last[x];last[x]=w;e[w].o=y;e[w].l=z; } void dijkstra(long long s){ long long x,y; memset(dist,42,sizeof(dist));//初始化所有距离 dist[s]=0; arr po; po.di=0; po.id=s; q.push(po);//压入起点 memset(flag,0,sizeof(flag)); while(q.size()>0){ x=q.top().id; if(x==n)yes=1;//判断是否能到终点 q.pop();//拿出最近的点 if(flag[x]==1)continue;//如果这个点已经拿出来过了，则最短的已经更新，当前的此点距离一定不是最短的 flag[x]=1;//将当前点标记成已经更新过 for(int w1=last[x];w1;w1=e[w1].n){//搜索它可以更新出去的点 y=e[w1].o; if(dist[x]+e[w1].l<dist[y]){//如果可以更新这个点的答案 pre[y]=x;//记录下这个点的前导 dist[y]=dist[x]+e[w1].l;//更新距离 po.id=y; po.di=dist[y]; q.push(po);//将这个点的最新情况放入小根堆，当前点旧的信息将来会自动淘汰 } } } } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&x,&y,&z); add(x,y,z);//增加双向边 add(y,x,z); } dijkstra(1);//运行dijkstra if(yes==0){ cout<<-1<<endl; return 0; } long long now=n; while(now){//用栈记录从终点到起点的情况 st.push(now); now=pre[now]; } while(st.size()>0){//反向输出 cout<<st.top()<<" "; st.pop(); } return 0; }