Annual Parade

All submissions for this problem are available.
In the magic land, there is an annual parade hold on each spring.
There are N cities in magic land, and M directed roads between cities.
On the parade, there will be some(may be 0) heroes travel in this land, for each hero:
He start at city begin[i], traveling to some cities, and finish at city end[i]. Note that: begin[i] may be equals to end[i], but he must at least moved to another city during this travel. He can go on one road many times, but it will have a cost for each time.
The cost of this parade is the sum of these items:
1. The sum of costs by traveling on roads. (If a road is passed by k heroes, then it must be count k times.)
2. If for a hero, he ended at a city that not equals to his start city, i.e. begin[i] != end[i], then it will cost C dollars to move him back to his home.
3. If for a city, there is no heroes visited, then we must pay for the citizen C dollars as compensate.
The value of C may change every year, and we can predict this value in the following K years.
Your task is: calculate the minimal cost of each year.
Input
In the first line, there are 3 integers: N, M and K.
In the following M lines:
there will be 3 integers: S[i], T[i], and V[i], describing a directed road from S[i] to T[i], cost V[i] dollars.
In the next K lines:
There will be an integer: C[i], describing the value of C in that year.
Output
Output K lines:
each line contain an integer, corresponding to the minimal cost of each year.
Constraints
2 <= N <= 250
1 <= M <= 30000
1 <= K <= 10000
S[i] != T[i], 1 <= S[i], T[i] <= N
1 <= V[i] <= 10000
1 <= C <= 10000
Note that: there may be more than 1 road between a certain pair of cities.
Example
Input: 6 5 3 1 3 2 2 3 2 3 4 2 4 5 2 4 6 2 1 5 10 Output: 6 21 32
Explanation
In the first year, since C is very small, an optimal solution is: no hero travel, we pay 1 dollar for each city as compensate.
In the second year, an optimal solution is: One hero traveling in the path: 1>3>4>5. We pay 2+2+2=6 dollars for the roads, 5 dollars for taking him back to city 1, and pay 5 dollars for city 2 and 6 as compensate.
In the third year, one optimal solution is: One hero traveling in the path: 1>3>4>5, and another hero traveling in the path: 2>3>4>6.
Author:  cgy4ever 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/PARADE 
Tags  binarysearch, cgy4ever, floydwarshall, mincostflow, sep12 
Date Added:  3082012 
Time Limit:  0.618667 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions