977 . 盜墓筆記：黃泉之路
Description
千年古墓重現世間，傳說中埋藏著帝王生前的無盡財寶。但這座墓地佈滿機關與陷阱，通道之間只有單向可以通行，一旦通過就無法回頭。
你作為盜墓小隊的首領，帶領隊員們深入墓穴。每個房間中都藏有一定價值的寶物，而你只能選擇從某一個房間出發，沿著通道一路向前探索，並在某一個房間停下（可以跟你出發的房間為同一個）。你必須拿取所有你經過的房間的寶物（包含第一個到最後一個房間）。由於你不想空手而歸，所以你至少會拿走一個寶物（即你選擇出發的房間中的寶物）。
這座墓地有 $N$ 個房間，編號成 $1$ 到 $N$ 。
你的目標是從所有可行的路徑中，找出能取得的最大寶物總價值。
Input Format
第一行包含兩個整數 $N, M$ 。
第二行有 $N$ 個整數 $V_1, V_2, \ldots, V_N$ ， $V_i$ 代表第 $i$ 個房間中寶物的價值。
接下來的 $M$ 行，每行會有兩個整數 $x, y$ ，代表有一條單向通道從房間 $x$ 通到房間 $y$ 。
- $1 \le N \le 10^ 6$
- $0 \le M \le \min(10^ 6, \frac{n(n-1)}{2})$
- $-10^ 6 \le V_i \le 10^ 6$
- $1 \le x, y \le N$, $x \neq y$
- $(x, y)$ 不會重複
- 保證整座墓地中不會出現環
Output Format
輸出一個整數，代表最大寶物總價值。
Sample Input 1
5 6 8 10 7 1 5 3 4 4 1 2 5 2 1 5 1 3 5
Sample Output 1
23
Sample Input 2
8 8 6 10 -1 0 -8 -3 1 10 6 3 7 1 4 2 7 8 6 5 1 4 7 2 8 1
Sample Output 2
27
Hints
範例１如圖所示，其中能獲得最大價值的路徑為 $2 \to 5 \to 1$，最大寶物總價值為 $23$。
範例２如圖所示，其中能獲得最大價值的路徑為 $7 \to 8 \to 1 \to 4 \to 2$，最大寶物總價值為 $27$。
Problem Source
YTP 2025 國中組程式挑戰營 p7
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 0~17 | 無額外限制 | 20 |