输入数据给出一个有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么?