TopCoder

asuka
酸欠少女

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

88.9% (8/9)

Tags

Description

現在有一張 N 個點 M 條邊的有向圖,代表有 N 個城市(編號 1N), 由 M 條有向道路連接(城市之間有可能不連通,無法抵達)。
小 D 是一個旅行商人,他會在旅途的同時做生意賺錢。而且小 D 非常精明,他在地圖上紀錄好了經過每條道路他可以獲利多少錢,但是由於有山賊出沒,有些道路的獲利可能是負的。

小 D 好奇是否存在一條從某城市出發,且最後回到該城市的旅途可以保證賺到錢,同一條道路可以重複經過。請你寫程式幫助小 D 發大財。

Input Format

第一行包含兩個整數 N,M 以空白隔開,代表有 N 座城市,有 M 條道路。
第二行至第 M+1 行,每行有三個數字 a,b,c 以空白隔開,代表城市 a 和城市 b 之間有一條可以獲利 c 元的單向道路。

  • 3N2000
  • 1Mmin(N(N1), 2000)
  • 1a,bNab
  • |c|104
  • 所有 (a,b) 的有序對(順序重要,(a,b)(b,a) 不同)不重覆。

Output Format

輸出一行 YESNO 代表是否存在一條從某城市出發,且最後回到該城市的旅途可以保證賺到錢。

Sample Input 1

10 11
1 2 6
2 3 -1
3 4 -1
4 5 -4
5 6 10
6 2 -5
7 6 8
5 8 2
3 9 1
9 10 1
10 4 -1

Sample Output 1

YES

Sample Input 2

3 2
1 2 -1
2 1 1

Sample Output 2

NO

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~50 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2
30 1000 524288 65536 2
31 1000 524288 65536 2
32 1000 524288 65536 2
33 1000 524288 65536 2
34 1000 524288 65536 2
35 1000 524288 65536 2
36 1000 524288 65536 2
37 1000 524288 65536 2
38 1000 524288 65536 2
39 1000 524288 65536 2
40 1000 524288 65536 2
41 1000 524288 65536 2
42 1000 524288 65536 2
43 1000 524288 65536 2
44 1000 524288 65536 2
45 1000 524288 65536 2
46 1000 524288 65536 2
47 1000 524288 65536 2
48 1000 524288 65536 2
49 1000 524288 65536 2
50 1000 524288 65536 2