777 . 小 D 發大財
TopCoder
Tags
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 \le N \le 2000$
- $1 \le M \le \min(N(N-1),\ 2000)$
- $1 \le a,b \le N$ 且 $a \neq b$
- $|c| \le 10^ 4$
- 所有 $(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 |