5 7 0 4
0 1 1
0 2 2
0 3 5
3 2 15
2 4 25
1 4 17
1 2 0
18
#include<bits/stdc++.h> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*f; } const int maxn=5e6+10; int n,m,c; int to[maxn],nxt[maxn],w[maxn]; int head[maxn]; int cnt=1; void add(int x,int y,int z) { to[cnt]=y; w[cnt]=z; nxt[cnt]=head[x]; head[x]=cnt++; } struct node { int x,d; bool operator <(const node& A) const { return d>A.d; } }; bool vis[maxn]; int dis[maxn]; priority_queue<node>q; node tmp; void dijkstra(int s) { memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); tmp.x=s,tmp.d=0; q.push(tmp); dis[s]=0; while(!q.empty()) { int x=q.top().x;q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(dis[y]>dis[x]+w[i]) { dis[y]=dis[x]+w[i]; tmp.x=y,tmp.d=dis[y]; q.push(tmp); } } } } int qd,zd; void inint(){ n=read(),m=read(); qd=read(),zd=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add(x,y,z); } } int main() { inint(); dijkstra(qd); printf("%d\n",dis[zd]); return 0; }
原文：https://www.cnblogs.com/lipu123/p/13302187.html