Home => ProblemSet => 5.1-17:单源最短路径
1354: 5.1-17:单源最短路径
Time Limit: 2 Sec Memory Limit: 128 MB Submit: 0 Solved: 2[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
Input
第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。
接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。
Output
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31−1。
Sample Input Copy
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
Sample Output Copy
0 2 4 3
HINT
对于 20% 的数据：1≤n≤5，1≤m≤15；
对于 40% 的数据：1≤n≤100，1≤m≤10^4；
对于 70% 的数据：1≤n≤1000，1≤m≤10^5；
对于 100% 的数据：1≤n≤10^4，1≤m≤5×10^5，保证数据随机。
对于 40% 的数据：1≤n≤100，1≤m≤10^4；
对于 70% 的数据：1≤n≤1000，1≤m≤10^5；
对于 100% 的数据：1≤n≤10^4，1≤m≤5×10^5，保证数据随机。