【c++图论】P3371 【模板】单源最短路径

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 mm 行每行包含三个整数 u,v,wu,v,w，表示一条 u \to vu→v 的，长度为 ww 的边。

输出格式

输出一行 nn 个整数，第 ii 个表示 ss 到第 ii 个点的最短路径，若不能到达则输出 2^{31}-1231−1。

输入输出样例

输入 #1复制

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 #1复制

0 2 4 3

说明/提示

【数据范围】 对于 20\%20% 的数据：1\le n \le 51≤n≤5，1\le m \le 151≤m≤15； 对于 40\%40% 的数据：1\le n \le 1001≤n≤100，1\le m \le 10^41≤m≤104； 对于 70\%70% 的数据：1\le n \le 10001≤n≤1000，1\le m \le 10^51≤m≤105； 对于 100\%100% 的数据：1 \le n \le 10^41≤n≤104，1\le m \le 5\times 10^51≤m≤5×105，1\le u,v\le n1≤u,v≤n，w\ge 0w≥0，\sum w< 2^{31}∑wb=1,b->c=1,a->c=5，那么a-b-c的值要小于a-c，所以需要绕路 dis[v]=dis[x]+e[i].w; if(!vis[v]){/如果这个点没走过 vis[v]=1; q.push(v);//入队 } } } } } int main(){ cin>>n>>m>>s; for(int i=1;i>a>>b>>c; addedge(a,b,c);//记录数据 } spfa();//开始处理 for(int i=1;i