CONTCITY - Contaminated City

no tags 

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 i-th
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: 2015-08-09 11:15:39

a very nice problem ;-)

:D: 2012-05-21 13:33:32

I thought you retired ;)

[Rampage] Blue.Mary: 2012-05-21 09:09:10

It seems that the helicopter can stay there for infinitely long time.

Patrick Klitzke: 2012-05-11 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: 2012-02-07 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): 2012-02-07 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?

Put another way, in the case
2 1 1
1
0
1 2 1
1 2 1
Can they be rescued in only 1 day?


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