AIOC Banner

Problem: The Virus

Want to try solving this problem? You can submit your code online if you log in or register.

The Virus

Input File: standard input
Output File: standard output

Time Limit: 1 second
Memory Limit: 32 MB

No one knows how it all started, just that it happened so quickly. Two weeks ago you were watching the news about political problems in far away nations, today you are on the run from your own neighbours who have fallen victim to The Virus. There is no known cure for The Virus which is plaguing the nation - once a person has contracted it, they cannot be cured. Thankfully though, Dr. Yes has come to you with a curious biological weapon, which is used to deploy a vaccine against the virus. Using his weapon, the vaccine can be administered to everybody within a city instantly, effectively stopping the spread of The Virus within that city.

The eccentric Dr. Yes hastily describes to you in a raspy voice his plan to save the nation. Together you will travel to every city in the country and use the weapon on each city, saving those you can by vaccinating the healthy individuals against The Virus.

Each city's mayor has determined the rate of spread of The Virus in their city, measured in victims per hour. You need to perform this rescue option to minimise the number of victims. Some roads take longer to travel on than others, and each wasted hour means more people lost to The Virus. Given a map of all the roads in the country and the number of citizens in each city falling victim to The Virus every hour, determine a route passing through every city such that the total number of people infected by The Virus is as small as possible. Furthermore, in these dangerous times with thieves and murderers abound, you must not travel on any road more than twice.

There exist N cities in the country, and N-1 bi-directional roads which connect the cities such that there is a path from every city to every other city. You know from your days as an informatics student that the graph formed is called a "tree". You also may assume that city populations are sufficiently large that they will never lose all their citizens to The Virus.

You are about to start coding, when Dr. Yes interrupts you with a final remark.

"Remember, lives are in your hands. Code fast and we will be the heroes of tomorrow."


The first line of input will contain a single integer N, the number of cities (1 ≤ N ≤ 100 000). The cities are numbered from 1 to N. You must commence your rescue operation in city 1.

The second line of input will contain N non-negative integers. The ith integer represents the number of citizens succumbing to The Virus each hour in city i. This value will be at most 100.

This will be followed by N-1 lines of input. Each line will contain three space-separated integers a, b and h, representing a road from city a to city b that takes h hours to travel (1 ≤ h ≤ 100).

For 60% of the available marks, N ≤ 1 000.

For 20% of the available marks, N ≤ 10.


Output should consist of one line with a single integer: the minimum number of victims of The Virus before every city is saved.

Sample Input

9 10 2 5 1
1 2 2
1 4 4
3 4 3
4 5 5

Sample Output



The optimal path is:

1 --> 22 hours
2 --> 12 hours
1 --> 44 hours
4 --> 33 hours
3 --> 43 hours
4 --> 55 hours

City Hours until saved Infected each hour Citizens lost to The Virus
1 0 9 0
2 2 10 20
3 11 2 22
4 8 5 40
5 19 1 19
      Total: 101


The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2021

Page generated: 21 September 2021, 10:20am AEST