1266: 最短路径 之 SPFA算法

    输入数据给出一个有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的最短路的长度.

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