题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：
第一行包含三个整数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。保证数据随机。
对于真正 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。
样例说明：
题解：真·模板题，真的只是套模板啊啊啊！dijkstra算法
#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> typedef long long ll; const int oo=2147483647; using namespace std; struct node{ int z; int val; int nexty; }e[500005]; int head[10004]; int cnt=0; inline void add(int a,int b,int c){ cnt++; e[cnt].z=b; e[cnt].val=c; e[cnt].nexty=head[a]; head[a]=cnt; } bool v[10004]; ll dis[20000]; int n,m,s,a,b,c; int main(){ freopen("3371.in","r",stdin); freopen("3371.out","w",stdout); scanf("%d %d %d",&n,&m,&s); for(int i=1;i<=n;i++) dis[i]=oo; for(int i=0;i<m;i++){ scanf("%d %d %d",&a,&b,&c); add(a,b,c); } int curr=s; dis[s]=0; ll mn; while(!v[curr]){ v[curr]=true; for(int i=head[curr];i!=0;i=e[i].nexty){ if(!v[e[i].z]&&dis[e[i].z]>dis[curr]+e[i].val) dis[e[i].z]=dis[curr]+e[i].val; } mn=oo; for(int i=1;i<=n;i++){ if(!v[i]&&mn>dis[i]){ mn=dis[i]; curr=i; } } } for(int i=1;i<=n;i++) printf("%lld ",dis[i]); return 0; }