CCO '24 P1 - Treasure Hunt - DMOJ: Modern Online Judge

CCO '24 P1 - Treasure Hunt

View as PDF

Submit solution

All submissions

Best submissions

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$ ~N~ islands connected by a network of $M$ ~M~ sea routes. The $i$ ~i~-th sea route connects islands $a_i$ ~a_i~ and $b_i$ ~b_i~ and costs $c_i$ ~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$ ~N~ islands and has determined that the $i$ ~i~-th island contains a treasure chest with $v_i$ ~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$ ~x~ and ending at island $y$ ~y~. At the end of his journey, he will open the chest at island $y$ ~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$ ~x~, he would like to know the maximum possible number of coins he can earn out of all journeys starting at island $x$ ~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$ ~N~ and $M$ ~M~.

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

The next $M$ ~M~ lines each contain three space-separated integers $a_i, b_i$ ~a_i, b_i~ $(1 \le a_i, b_i \le N)$ ~(1 \le a_i, b_i \le N)~, and $c_i$ ~c_i~ $(0 \le c_i \le 10^9)$ ~(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$ ~1 \le N \le 3\,000~	$0 \le M \le 3\,000$ ~0 \le M \le 3\,000~	None
5	marks	$1 \le N \le 10^6$ ~1 \le N \le 10^6~	$0 \le M \le 10^6$ ~0 \le M \le 10^6~	For all $i$ ~i~, either $c_i = 0$ ~c_i = 0~ or $c_i = 10^9$ ~c_i = 10^9~
7	marks	$1 \le N \le 10^6$ ~1 \le N \le 10^6~	$0 \le M \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$ ~1 \le N \le 10^6~	$0 \le M \le 10^6$ ~0 \le M \le 10^6~	None

Output Specification

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

Sample Input 1

Sample Output 1

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$ ~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$ ~9 - 2 - 3 = 4~ coins and is the best possible net profit.

Comments

1

CubixularHelix commented on Sept. 25, 2024, 6:54 p.m.

:(

0

lucaski2 commented on Sept. 17, 2024, 5:51 p.m.

Is there an editorial

-2

htoshiro commented on Sept. 20, 2024, 6:22 p.m. ← edited →

https://cemc.uwaterloo.ca/resources/past-contests?grade=All&academic_year=All&contest_category=80. These are 2024 CCO solutions posted by the CEMC. Please refer to these. If you have more questions, you can join the DMOJ Discord server for more help.

-1

whoislaura commented on Aug. 18, 2024, 7:37 p.m. ← edited →

.