User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

45.5% (10/22)

Description

給定一張有向圖,請檢查這張圖是否存在負環
負環定義:一個環上的邊權重總和為負

Input Format

第一行有兩個數字 $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$ 出發到達

Output Format

輸出只有一行,假設有負環輸出 Yes,反之輸出 No

Sample Input 1

5 10
1 0 -10
4 2 -9
2 3 -10
1 2 1
3 2 9
2 1 -6
4 3 7
2 1 -5
4 3 -7
2 1 -3

Sample Output 1

Yes

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1