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

第一行:&nbsp 点数N(2&nbsp < =&nbsp N&nbsp < =&nbsp 1,000),&nbsp 边数M(M&nbsp < =&nbsp 100,000),&nbsp 源点S(1&nbsp < =&nbsp S&nbsp < =&nbsp N);
以下M行,&nbsp 每行三个整数a,&nbsp b,&nbsp c表示点a,&nbsp b(1&nbsp < =&nbsp a,&nbsp b&nbsp < =&nbsp N)之间连有一条边,&nbsp 权值为c(-1,000,000&nbsp < =&nbsp c&nbsp < =&nbsp 1,000,000)

如果存在负权环,&nbsp 只输出一行-1,&nbsp 否则按以下格式输出
共N行,&nbsp 第i行描述S点到点i的最短路:&nbsp
如果S与i不连通,&nbsp 输出NoPath;
如果i&nbsp =&nbsp S,&nbsp 输出0;
其他情况输出S到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
 · · \n
 · · \n
 · · \n
 · ·  \n
 · · \n
 · · \n
 · · \n
 · · \n
 · · \n

0
6
4
-3
-2
7
 \n
 \n
 \n
  \n
  \n
 \n

做这道题时,&nbsp 你不必为超时担心,&nbsp 不必为不会算法担心,&nbsp 但是如此“简单”的题目,&nbsp 你究竟能ac么?