2788: 「一本通 3.3 练习 3」Easy SSSP
Memory Limit：512 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：13
Solved：5
Description
原题来自：Vijos P1053
输入数据给出一个有 NNN 个节点，MMM 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 000，就说这条路是一个负权回路。
如果存在负权回路，只输出一行 −1-1−1；如果不存在负权回路，再求出一个点S到每个点的最短路的长度。约定：SSS 到 SSS 的距离为 000，如果 SSS 与这个点不连通，则输出 NoPath。
Input
第一行三个正整数，分别为点数 NNN，边数 MMM，源点 SSS；
以下 MMM 行，每行三个整数 a,b,ca, b, ca,b,c，表示点 a,ba, ba,b 之间连有一条边，权值为 ccc。
Output
如果存在负权环，只输出一行 −1-1−1，否则按以下格式输出：
共 NNN 行，第 iii 行描述 SSS 点到点 iii 的最短路：
- 如果 SSS 与 iii 不连通，输出
NoPath； - 如果 i=Si = Si=S，输出 000。
- 其他情况输出 SSS 到 iii 的最短路的长度。
HINT
样例输入
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样例输出
0
6
4
-3
-2
7对于全部数据，2≤N≤1000,1≤M≤105,1≤a,b,S≤N,∣c∣≤1062le Nle 1000,1le Mle 10^5,1le a,b,Sle N,|c|le 10^62≤N≤1000,1≤M≤105,1≤a,b,S≤N,∣c∣≤106。
做这道题时，你不必为超时担心，不必为不会算法担心，但是如此「简单」的题目，你究竟能 AC 么？