题目描述
原题来自：Vijos P1053
输入数据给出一个有
N
N 个节点，
M
M 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于
0
0，就说这条路是一个负权回路。
如果存在负权回路，只输出一行
-1
−1；如果不存在负权回路，再求出一个点
S
S 到每个点的最短路的长度。约定：
S
S 到
S
S 的距离为
0
0，如果
S
S 与这个点不连通，则输出 NoPath。
输入
第一行三个正整数，分别为点数
N
N，边数
M
M，源点
S
S；
以下
M
M 行，每行三个整数
a, b, c
a,b,c，表示点
a, b
a,b 之间连有一条边，权值为
c
c。
输出
如果存在负权环，只输出一行
-1
−1，否则按以下格式输出：
共
N
N 行，第
i
i 行描述
S
S 点到点
i
i 的最短路：
如果
S
S 与
i
i 不连通，输出 NoPath；
如果
i = S
i=S，输出
0
0。
其他情况输出
S
S 到
i
i 的最短路的长度。
样例输入
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
样例输出
0
6
4
-3
-2
7
提示
数据范围与提示
对于全部数据，
2\le N\le 1000,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^6
2≤N≤1000,1≤M≤105,1≤a,b,S≤N,∣c∣≤106。
来源/分类
ybttg 最短路 负环