APIO '13 P2 - Toll - Olympiads Online Judge

APIO '13 P2 - Toll

Points: 35 (partial)

Time limit: 2.0s

Memory limit: 128M

Problem type

Happyland can be described by a set of $N$ ~N~ towns (numbered $1$ ~1~ to $N$ ~N~) initially connected by $M$ ~M~ bidirectional roads (numbered $1$ ~1~ to $M$ ~M~). Town $1$ ~1~ is the central town. It is guaranteed that one can travel from town $1$ ~1~ to any other town through these roads. The roads are toll roads. A user of the road $i$ ~i~ has to pay a toll fee of $c_i$ ~c_i~ cents to the owner of the road. It is known that all of these $c_i$ ~c_i~'s are distinct. Recently, $K$ ~K~ additional new roads are completed and they are owned by a billionaire Mr Greedy. Mr Greedy can decide the toll fees (not necessarily distinct) of the new roads, and he has to announce the toll fees tomorrow.

Two weeks later, there will be a massive carnival in Happyland! Large number of participants will travel to the central town and parade along the roads. A total of $p_j$ ~p_j~ participants will leave from town $j$ ~j~ and travel toward the central town. They will only travel on a set of selected roads, and the selected roads will be announced a day before the event. By an old tradition, the roads are to be selected by the richest person in Happyland, who is Mr Greedy. Constrained by the same tradition, Mr Greedy must select a set of roads that minimizes the sum of toll fees in the selected set and yet at the same time allow anyone to travel from town $j$ ~j~ to town $1$ ~1~ (hence, the selected roads form a "minimum spanning tree" where the toll fees are the weights of the corresponding edges). If there are multiple such sets of roads, Mr Greedy can select any set as long as the sum is minimum.

Mr Greedy is well-aware that the revenue he received from the $K$ ~K~ new roads does not solely depend on the toll fees. The revenue from a road is actually the total fee collected from people who travel along the road. More precisely, if $p$ ~p~ people travel along road $i$ ~i~, the revenue from the road $i$ ~i~ is the product $c_ip$ ~c_ip~. Note that Mr Greedy can only collect fees from the new roads since he does not own any of the old roads.

Mr Greedy has a sneaky plan. He plans to maximize his revenue during the carnival by manipulating the toll fees and the roads selection. He wants to assign the toll fees to the new roads (which are to be announced tomorrow), and select the roads for the carnival (which are to be announced a day before the carnival), in such a way that maximizes his revenue from the $K$ ~K~ new roads. Note that Mr Greedy still has to follow the tradition of selecting a set of roads that minimizes the sum of toll fees.

You are a reporter and want to expose his plan. To do so, you have to first write a program to determine how much revenue Mr Greedy can make with his sneaky plan.

Subtasks

Your program will be tested on 5 sets of instances as follows:

( $16$ ~16~ points) $N \le 10$ ~N \le 10~, $M \le 20$ ~M \le 20~ and $K = 1$ ~K = 1~.
( $18$ ~18~ points) $N \le 30$ ~N \le 30~, $M \le 50$ ~M \le 50~ and $K \le 10$ ~K \le 10~.
( $22$ ~22~ points) $N \le 1\,000$ ~N \le 1\,000~, $M \le 5\,000$ ~M \le 5\,000~ and $K \le 10$ ~K \le 10~.
( $22$ ~22~ points) $N \le 100\,000$ ~N \le 100\,000~, $M \le 300\,000$ ~M \le 300\,000~ and $K \le 15$ ~K \le 15~.
( $22$ ~22~ points) $N \le 100\,000$ ~N \le 100\,000~, $M \le 300\,000$ ~M \le 300\,000~ and $K \le 20$ ~K \le 20~.

Input

Your program must read from the standard input. The first line contains three space-separated integers $N$ ~N~, $M$ ~M~ and $K$ ~K~. The next $M$ ~M~ lines describe the initial $M$ ~M~ roads. The $i$ ~i~-th of these lines contains space-separated integers $a_i$ ~a_i~, $b_i$ ~b_i~ and $c_i$ ~c_i~, indicating that there is a bidirectional road between towns $a_i$ ~a_i~ and $b_i$ ~b_i~ with toll fee $c_i$ ~c_i~. The next $K$ ~K~ lines describe the newly built $K$ ~K~ additional roads. The $i$ ~i~-th of these lines contains space-separated integers $x_i$ ~x_i~ and $y_i$ ~y_i~, indicating that there is a new road connecting towns $x_i$ ~x_i~ and $y_i$ ~y_i~. The last line contains $N$ ~N~ space-separated integers, the $j$ ~j~-th of which is $p_j$ ~p_j~, the number of people from town $j$ ~j~ traveling to town $1$ ~1~.

The input also satisfies the following constraints.

$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~.
$1 \le K \le 20$ ~1 \le K \le 20~.
$1 \le M \le 300\,000$ ~1 \le M \le 300\,000~.
$1 \le c_i, p_j \le 10^6$ ~1 \le c_i, p_j \le 10^6~ for each $i$ ~i~ and $j$ ~j~.
$c_i \neq c_{i^\prime}$ ~c_i \neq c_{i^\prime}~, if $i \neq i^\prime$ ~i \neq i^\prime~.
Between any two towns, there is at most one road (including newly built ones).

Output

Your program must write to the standard output a single integer, which is the maximum total revenue obtainable.

Sample Input

5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50

Sample Output

$\text{[math]}$

Explanation for Sample Output

In this sample, Mr Greedy should set the toll fee of the new road $(1,3)$ ~(1,3)~ to be $5$ ~5~ cents. With this toll fee, he can select the roads $(3,5)$ ~(3,5)~, $(1,2)$ ~(1,2)~, $(2,4)$ ~(2,4)~ and $(1,3)$ ~(1,3)~ to minimize sum of toll fees, which is $14$ ~14~ cents. $30$ ~30~ people from town $3$ ~3~ and $50$ ~50~ people from town $5$ ~5~ will pass through the new road to town $1$ ~1~ and hence he can collect an optimal revenue of $(30 + 50) \times 5 = 400$ ~(30 + 50) \times 5 = 400~ cents.

If, on the other hand, the toll fee of the new road $(1,3)$ ~(1,3)~ is set to be $10$ ~10~ cents. Now, constrained by the tradition, Mr Greedy must select $(3,5)$ ~(3,5)~, $(1,2)$ ~(1,2)~, $(2,4)$ ~(2,4)~ and $(2,3)$ ~(2,3)~ as this is the only set that minimizes the sum of toll fees. Hence, no revenue will be collected from the new road $(1,3)$ ~(1,3)~ during the carnival.

Comments

There are no comments at the moment.