负权图最短路
题目描述
输入数据给出一个有 n 个节点，m 条边的带权有向图。 判断从起点s开始的路径是否会抵达负环，如果能只输出一行 −1； 如果从起点s无法到达负环，或不存在负环，则输出起点s到达各点的最短路值，无法到达的点对应输出NoPath。
输入格式
第一行三个正整数，分别为点数 n，边数 m，起点s； 以下 m 行，每行三个整数 u,v,w，表示点 u到v 之间连有一条边，权值为 w。
输出格式
如果存在起点能到达的负权环，只输出一行 −1，否则按以下格式输出： 共 n 行，第 i 行描述 s 点到点 i 的最短路： 如果 S 与 i 不连通，输出 NoPath； 如果 i=S，输出 0。 其他情况输出 S 到 i 的最短路的长度。
5 4 1
1 2 1
3 4 -1
4 5 1
5 3 -2
0
1
NoPath
NoPath
NoPath
数据规模与约定
对于全部数据，,。