SPFA模板

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int cnt,st,ed,s,t,w,h[10005],dis[10005],stack[10005]; int q[40005]; struct Node{ int to,w,next; }edge[10005];//10005,1005 void add(int s,int t,int v) { cnt++; edge[cnt].to=t; edge[cnt].w=v; edge[cnt].next =h[s]; h[s]=cnt; } int spfa() { int head=1,tail=1; q[1]=st; while(head<=tail) { int u=q[head]; for(int i=h[u];i;i=edge[i].next) { int v=edge[i].to; if(edge[i].w+dis[u]<dis[v]) { dis[v]=edge[i].w+dis[u]; if(!stack[v]) { stack[v]=1; tail++; q[tail]=v; } } } head++; stack[u]=0;//退出栈 } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&s,&t,&w); add(s,t,w); } scanf("%d%d",&st,&ed);//起点，终点 memset(dis,1,sizeof dis); dis[st]=0; spfa(); cout<<dis[ed]<<endl; }

//三个点两条边，问2到3最短路 3 2 2 1 10 1 3 5 2 3 ?

ans:15