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.
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 K lines:
each line contain an integer, corresponding to the minimal cost of each year.
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.
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
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.
|Tags||binary-search, cgy4ever, floyd-warshall, min-cost-flow, sep12|
|Time Limit:||0.618667 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.