CONTCITY  Contaminated City
In a far away country there is a city facing a big problem. The city is plagued by a deadly gas. Many
people have died, but there are groups of survivors at places around the city. Between these places
there are roads connecting two distinct places that can still be traversed safely. These roads can be
traversed in both directions. It's known the number of days necessary to traverse each road and the
two places that it connects. It's also known the number of survivors at each location. Each survivor
can get to other places following a sequence of roads.
The mayor will send several helicopters to rescue these people, each having a capacity, a limit on
the number of crew (people that it can rescue). Each helicopter will land on a certain day and place.
You should answer an important question for the mayor. How many days are needed to rescue all
survivors? If it's not possible to rescue all people you should answer how many of them can be
rescued.
Input
The first line of input file have the number of test cases T (T <= 40).
The first line of each test case have N, M, and H, the number of places considered, the number of
roads between the places and the number of helicopters that will be sent, respectively. Each place is
uniquely identified by a number between 1 and N. The next N lines will have N integers, the ith
line have the number of survivors in place i, Xi. Each of next M lines will have three numbers Aj,
Bj and Dj, meaning that there is a way between places Aj and Bj that last Dj days to traverse. The
input can contain several roads between the same pair of places. Each of next H lines will have
three integers Dh, Ph, and Ch (in this order), meaning that a helicopter with capacity Ch will arrive
at place Ph at day Dh. The sum of survivors will not be more than 200. If a survivor can get a
helicopter following a sequence of roads, the total time to get the helicopter will not be more than
1000.
Constraints:
1 <= N, H <= 50
1 <= M <= 1500
1 <= Aj, Bj, Ph <= N
1 <= Dj, Dh <= 1000
1 <= Ch <= 200
0 <= Xi <= 200
Output
For each test case there is one line in output. If all people can be rescued "All people can be rescued
in D day(s) ." should be printed, where D is the minimum number of days to rescue all people. If it
is impossible to rescue all people "X survivor(s) can be rescued." should be printed, where X is the
maximum number of survivors that can be rescued.
Example
Input: 2
4 4 4
3
4
5
6
1 2 7
2 3 3
3 4 3
4 1 4
4 4 7
6 3 2
5 2 3
3 1 6
4 2 3
2
2
3
1
1 4 3
2 3 3
2 4 2
3 2 4
3 3 2 Output: All people can be rescued in 6 day(s).
7 survivor(s) can be rescued.
hide comments
Rishav Goyal:
20150809 11:15:39
a very nice problem ;) 

:D:
20120521 13:33:32
I thought you retired ;) 

[Rampage] Blue.Mary:
20120521 09:09:10
It seems that the helicopter can stay there for infinitely long time. 

Patrick Klitzke:
20120511 18:45:18
Does the helicopter stay for only one day, it seems to be but it is not stated anywhere. 

Fulano, Beltrano e Sicrano:
20120207 17:45:15
People start at day 0 and the answer to the second question is YES. The answer to the testcase is 1. 

Equipe Up (Cesar, Leonardo e Lucas):
20120207 16:43:29
Do people start walking at Day 0 or Day 1? And can people use a helicopter in the same day they arrived?

Added by:  Paulo Costa 
Date:  20120119 
Time limit:  0.184s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 