1814: 求最短路和判断负环

【题目描述】
　　给出一个有N(2≤N≤1,000)个节点，M(M≤100,000)条边的带权有向图. 要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.如果存在负权回路, 只输出一行-1;如果不存在负权回路, 再求出一个点S(1≤S≤N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.

【输入格式】
　　第一行: 点数N(2≤N≤1,000), 边数M(M≤100,000), 源点S(1≤S≤N);
　　以下M行, 每行三个整数a, b, c表示点a, b(1≤a, b≤N)之间连有一条边, 权值为c( -1,000,000≤c≤1,000,000)

【输出格式】
　　如果存在负权环, 只输出一行-1, 否则按以下格式输出
　　共N行, 第i行描述S点到点i的最短路:
　　如果S与i不连通, 输出NoPath;
　　如果i = S, 输出0;
　　其他情况输出S到i的最短路的长度

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

OUTPUT:
0
6
4
-3
-2
7