『算法-ACM 竞赛-图论』最短路-dijkstra（含路径输出）模板

#include<iostream>
#include<stack>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
struct Node
{
int var,next,val;
} edge[100000005];
int head[100005],tot,dis[100005],N,M;
int pre[100005]; //松弛数组
bool vis[100005]; //唯一定理
priority_queue<PII> Q; //大根堆优化
void add(int a, int b, int c)
{
edge[++tot].var = b;
edge[tot].val = c;
edge[tot].next = head[a];
head[a] = tot;
}
void init()//多组输入调用
{
tot=0;
memset(head,0,sizeof(head));
}
void dijkstra(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
while(Q.size()) Q.pop();
dis[s] = 0;
Q.push(make_pair(0,s));
while(!Q.empty())
{
int x=Q.top().second;
Q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x]; i; i=edge[i].next)
{
int y=edge[i].var;
if(dis[x]+edge[i].val<dis[y]) //图论三角不等式
{
dis[y]=dis[x]+edge[i].val;
if(!vis[y])
Q.push(make_pair(-dis[y],y));
pre[y]=x;
}
}

    }

}
int main()
{
int S,E;
init();
cin>>N>>M>>S>>E;
while(M--)
{
int x,y,z;
cin>>x>>y>>z;
add(x+1,y+1,z);
}
dijkstra(S+1);
if(dis[E+1]>0x3f000000)
{
cout<<"no answer"<<endl;
return 0;
}
cout<<dis[E+1]<<endl;
stack<int> ans;
for(int i=E+1;i!=-1;i=pre[i])
{
ans.push(i-1);
//cout<<i-1<<endl;
}
while(ans.size())
{
cout<<'v';
cout<<ans.top()<<" ";
ans.pop();
}
puts("");
}