6988: 「一本通 3.3 练习 3」Easy SSSP
[Creator : ]
Description
原题来自：Vijos P1053
输入数据给出一个有 N 个节点，M 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 0，就说这条路是一个负权回路。
如果存在负权回路，只输出一行 -1；如果不存在负权回路，再求出一个点 S 到每个点的最短路的长度。约定：S 到 S 的距离为 0，如果 S 与这个点不连通，则输出 NoPath。
输入数据给出一个有 N 个节点，M 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 0，就说这条路是一个负权回路。
如果存在负权回路，只输出一行 -1；如果不存在负权回路，再求出一个点 S 到每个点的最短路的长度。约定：S 到 S 的距离为 0，如果 S 与这个点不连通，则输出 NoPath。
Input
第一行三个正整数，分别为点数 N，边数 M，源点 S；
以下 M 行，每行三个整数 a, b, c，表示点 a, b 之间连有一条边，权值为 c。
以下 M 行，每行三个整数 a, b, c，表示点 a, b 之间连有一条边，权值为 c。
Output
如果存在负权环，只输出一行 -1，否则按以下格式输出：
共 N 行，第 i 行描述 S 点到点 i 的最短路：
共 N 行，第 i 行描述 S 点到点 i 的最短路：
- 如果 S 与 i 不连通，输出 NoPath；
- 如果 i = S，输出 0。
- 其他情况输出 S 到 i 的最短路的长度。
Constraints
对于全部数据，$2\le N\le 1000,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^6$。
Sample 1 Input
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4
Sample 1 Output
0
6
4
-3
-2
7