給定一張有向圖,請檢查這張圖是否存在負環
負環定義:一個環上的邊權重總和為負
第一行有兩個數字 $N, M$
接下來有 $M$ 行,每行三個數字 $u_i, v_i, w_i$,代表有一條邊從 $u_i$ 到 $v_i$ 且權重為 $w_i$
$N \le 5000, M \le 15000$
$0 \le u_i, v_i \lt N, |w_i| \le 10 ^ 5 $
所有點都可以由編號 $0$ 出發到達
輸出只有一行,假設有負環輸出 Yes
,反之輸出 No
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 |