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

Submit

Status

Ranklist

57 . 欠債 5 億日圓頻道