洛谷P3371【模板】单源最短路径
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式：
第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。
输出格式：
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）
时空限制：1000ms,128M
数据规模：
对于20%的数据：N<=5，M<=15
对于40%的数据：N<=100，M<=10000
对于70%的数据：N<=1000，M<=100000
对于100%的数据：N<=10000，M<=500000
不多说，复习一下代码。
// luogu-judger-enable-o2 #include<iostream> #include<stdio.h> #include<cstring> #include<stdlib.h> #include<queue> #include<algorithm> using namespace std; #define MAXN 500100 #define ll long long queue<int> q; int dis[MAXN],have[MAXN]; struct edge{ int first; int next; int to; int quan; }a[MAXN+10]; int num=0,n,m,S; void addedge(int from,int to,int quan){ a[++num].to=to; a[num].quan=quan; a[num].next=a[from].first; a[from].first=num; } void spfa(int s){ while(!q.empty()) q.pop(); for(int i=1;i<=n;i++) dis[i]=2147483647; //memset(dis,127,sizeof(dis)); memset(have,0,sizeof(have)); have[s]=1,dis[s]=0; q.push(s); while(!q.empty()){ int now=q.front(); q.pop(); have[now]=0; for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to,quan=a[i].quan; if(dis[to]>dis[now]+quan){ dis[to]=dis[now]+quan; if(!have[to]){ have[to]=1; q.push(to); } } } } } int main(){ scanf("%d%d%d",&n,&m,&S); for(int i=1;i<=m;i++){ int x,y,z;scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } spfa(S); for(int i=1;i<=n;i++){ printf("%d ",dis[i]); } }
原文：https://www.cnblogs.com/renjianshige/p/9309480.html