CCO '24 P1 - Treasure Hunt

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem type

Perry the Pirate is sailing the seven seas! He has a map consisting of N islands connected by a network of M sea routes. The i-th sea route connects islands a_i and b_i and costs c_i coins to traverse in either direction. As it turns out, fighting off sea monsters can be quite expensive. In search of his next big plunder, Perry has scouted out each of the N islands and has determined that the i-th island contains a treasure chest with v_i coins inside.

It remains for him to plan out his next journey. He decides that he will sail through some (possibly empty) path of sea routes starting at island x and ending at island y. At the end of his journey, he will open the chest at island y and collect his well-earned booty.

There is one small problem though: Perry doesn't know what island he's currently on! Thus, for every possible starting island x, he would like to know the maximum possible number of coins he can earn out of all journeys starting at island x. Can you help him compute these values? You may assume Perry has enough coins to traverse any path of sea routes he chooses; he only cares about the net profit of his next journey.

Input Specification

The first line of input contains two space-separated integers N and M.

The second line of input contains N space-separated integers v_1, v_2, \ldots, v_N (0 \le v_i \le 10^9).

The next M lines each contain three space-separated integers a_i, b_i (1 \le a_i, b_i \le N), and c_i (0 \le c_i \le 10^9).

It is guaranteed that there is at most one sea route between any pair of islands and each sea route connects two distinct islands.

Marks Awarded Bounds on N Bounds on M Additional constraints
5 marks 1 \le N \le 3\,000 0 \le M \le 3\,000 None
5 marks 1 \le N \le 10^6 0 \le M \le 10^6 For all i, either c_i = 0 or c_i = 10^9
7 marks 1 \le N \le 10^6 0 \le M \le 10^6 Exactly one path of sea routes between any pair of islands
8 marks 1 \le N \le 10^6 0 \le M \le 10^6 None

Output Specification

Output N lines, where the x-th line contains the maximum possible net profit (in coins) of any journey starting at island x.

Sample Input 1

4 5
6 5 9 2
1 2 0
3 2 3
4 3 6
1 3 5
2 4 2

Sample Output 1

6
6
9
4

Explanation for Sample 1

For the first and third islands, it is best to just stay and open the chest on the island itself.

For the second island, Perry can travel to the first island and open the chest there.

This has a net profit of 6 - 0 = 6 coins and is the best possible net profit.

For the fourth island, Perry can travel to the second and then the third island and open the chest there.

This has a net profit of 9 - 2 - 3 = 4 coins and is the best possible net profit.


Comments