#include<bits/stdc++.h>using namespace std;int m,x,y,z,s,t,n,cnt;int head[100000],nxt[100000],to[1000000];int val[100000],dis[100000];bool f[100000];void add(int x,int y,int z){ cnt++; nxt[cnt]=head[x]; head[x]=cnt; val[cnt]=z; to[cnt]=y;}void spfa(){ queue<int>q; q.push(s); dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); f[u]=0; for(int i=head[u];i;i=nxt[i]) { if(dis[to[i]]>dis[u]+val[i]) { dis[to[i]]=dis[u]+val[i]; if(!f[to[i]]) { f[to[i]]=1; q.push(to[i]); } } } }}int main(){ scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } for(int i=1;i<=n;i++) dis[i]=0x7fffffff; spfa(); cout<<dis[t]; return 0;}
转载于:https://www.cnblogs.com/647Z/p/7355930.html
相关资源：JAVA上百实例源码以及开源项目