777 . 小 D 發大財

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

asuka
酸欠少女

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

88.9% (8/9)

Tags

apcsc apcsc-graph

Description

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

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

Input Format

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

  • 3≤N≤2000
  • 1≤M≤min(N(N−1), 2000)
  • 1≤a,b≤N 且 a≠b
  • |c|≤104
  • 所有 (a,b) 的有序對（順序重要，(a,b) 和 (b,a) 不同）不重覆。

Output Format

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

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
Submit
Back to Top