1185 - SCU-E
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 183
Solved: 51
- Description
- There are N citys in RAIN's country.
And there are M directed road between the N citys.
Now she is in the city 0.
And she want to go to city N-1.
But the bad FGJ donot want RAIN go to city N-1.
He can destroy some city to make it.
RAIN cannot go to the city which be destroyed.
Eeah city has a weight Wi to destroy.
FGJ cannot destroy the city 0.
Can you tell FGJ the minimal totle weight he must destroy? - Input
- The first line of the input is the number of test cases.
For each case there is M+1 lines.
The first line contains two integers N M.
The second line contains N-1 integers Wi ( 1 <= i < N ).
The next M lines each contains two integers P and Q,
represent there is a road from city P to city Q.
( 2 <= N <= 1000 , 0 <= M <= 10^5 , 0 <= P,Q < N , 0 <= Wi <= 10^5 )
There is a blank line before each test case. - Output
- For each test case output the answer on a line:
The minimal totle weight FGJ must destroy. - sample input
-
5 2 0 100 2 1 100 0 1 2 1 100 1 0 2 5 100 0 1 0 1 1 0 0 0 1 1 3 2 1 100 0 1 1 2
- sample output
-
0 100 0 100 1
- hint
- source
- SCUPC