Treasure 2 - MarisaOJ: Marisa Online Judge

Treasure 2

Time limit: 1000 ms
Memory limit: 256 MB
_Marisa has recently found a treasure map that leads her to an underground cave system consisting of $n$ rooms and $m$ one-way tunnels._ _After lighting up the cave, now Marisa need a plan to achieve as much treasure as possible._ The $i^{th}$ room has $A_i$ gold coins. Marisa can pick them up after visiting the room. She can visit any room more than once. She can start and end her journey at any room. What is the largest number of coins she can acquire. ### Input - The first line contains 2 integers $n,m$. - The second line contains $n$ integers $A_i$. - The next $m$ lines, each line contains two integers $u, v$, there is a tunnel between $u$ and $v$. ### Output - Print the maximum number of gold coins she can acquire. ### Constraints - $1 \le n,m \le 10^5$. - $1 \le A_i \le 10^9$. - $1 \le u,v \le n$. ### Example Input: ``` 3 3 1 2 3 1 2 2 3 3 1 ``` Output: ``` 6 ```
Topic
Graph
Dynamic Programming
Rating 1600
Solution (1) Solution