问题1648--单源最短路径

1648: 单源最短路径

时间限制: 1 Sec  内存限制: 128 MB
提交: 42  解决: 12
[提交] [状态] [讨论版] [命题人:]

题目描述

给出一张有向图，请输出从某一点出发到所有点的最短路径。

输入

第一行包含三个整数Ｎ、M、S，分别表示点的个数、有向边的个数、出发点的编号。接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条边有向边的出发点、目标点和长度。

输出

第一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i，则最短路径长度为0；若从点S无法到达点i，则最短路径长度为-1）。

样例输入 Copy 

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

样例输出 Copy 

0 2 4 3

提示

对于 20% 的数据：1≤n≤5，1≤m≤15；
对于 40% 的数据：1≤n≤100，1≤m≤104；
对于 70% 的数据：1≤n≤1000，1≤m≤105；
对于 100% 的数据：1≤n≤104 ，1≤m≤5×105 ，1≤u,v≤n， ∑w<231 ，保证数据随机。

来源/分类

最短路径 Bellman-Ford算法 SPFA算法 Dijkstra算法 Floyd算法 
[提交] [状态]