课件下载

描述

现在试试找到两点间的最短路吧。

输入格式

第一行包含三个整数 n , m , s , 表示图有 n 个节点和 m 条边，起点节点为 s 。

接下来 m 行，每行包含三个整数 u , v , w , 表示一条从 u 连向 v 的边的长度为 w。

输出格式

共一行 n 个整数，第 i 个整数表示起点节点 s 到节点 i 的最短路径，若不能到达则输出 2147483647 。

样例

5 7 0
0 1 1
0 2 3
0 3 2
1 3 1
2 4 2
3 4 4
4 1 5

0 1 3 2 5

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

0 2 4 3