P3639 [APIO2013] Toll

The Kingdom of Happiness can be described as a set of $N$ towns (numbered $1$ to $N$), initially connected by $M$ bidirectional roads (numbered $1$ to $M$). Town $1$ is the central town. It is guaranteed that starting from town $1$, one can reach any other town using these roads. All roads are toll roads: for road $i$, a user must pay $c_i$ cents to the road’s owner. It is known that all $c_i$ are pairwise distinct. Recently, $K$ new roads were built, all owned by $\text{Mr. Greedy}$. $\text{Mr. Greedy}$ can decide the toll for each new road (these tolls may be equal), and he must announce these tolls tomorrow. Two weeks later, the Kingdom of Happiness will host a grand carnival. A large number of participants will travel along the roads to the central town. In total, $p_j$ participants will start from town $j$ and head to town $1$. These people will travel only along a selected set of roads, and this selected set of roads will be announced the day before the event. According to an ancient custom, this set is chosen by the richest person in the kingdom, namely $\text{Mr. Greedy}$. By the same custom, the chosen set must minimize the sum of tolls of all selected roads and still ensure that everyone can travel from town $j$ to town $1$ (therefore, the selected roads form a “minimum spanning tree” with respect to the tolls as edge weights). If there are multiple such sets, $\text{Mr. Greedy}$ may choose any of them, as long as the total toll is minimal. $\text{Mr. Greedy}$ understands clearly that his revenue from the $K$ new roads depends not only on the toll values. The revenue of a road equals the total amount paid by all people who pass through it. More precisely, if $p$ people pass through road $i$, the revenue of road $i$ is the product $c_i \times p$. Note that $\text{Mr. Greedy}$ can only collect tolls from the new roads, since the original roads are not his. $\text{Mr. Greedy}$ has a scheme. He plans to maximize his revenue by manipulating the tolls and the choice of roads. He wants to set the toll for each new road (to be announced tomorrow) and choose the roads used for the carnival (to be announced the day before the carnival) so that his total revenue from the $K$ new roads is maximized. Note that $\text{Mr. Greedy}$ must still follow the custom of selecting a road set with the minimum total toll. You are a journalist and you want to expose his plan. To do this, you must first write a program to determine how much revenue $\text{Mr. Greedy}$ can obtain through his scheme.

Your program must read from standard input. The first line contains three space-separated integers $N, M, K$. The next $M$ lines describe the initial $M$ roads. In these $M$ lines, the $i$-th line contains space-separated integers $a_i, b_i, c_i$, indicating a bidirectional road between $a_i$ and $b_i$ with toll $c_i$. The next $K$ lines describe the $K$ newly built roads. In these $K$ lines, the $i$-th line contains space-separated integers $x_i$ and $y_i$, indicating a new road connecting towns $x_i$ and $y_i$. The last line contains $N$ space-separated integers, where the $j$-th is $p_j$, the number of people traveling from town $j$ to town $1$. Constraints: $1 \leq N \leq 10^5, 1 \leq K \leq 20, 1 \leq M \leq 3 \times 10^5$. For each $i$ and $j$, $1 \leq c_i, p_j \leq 10^6$, and if $i \neq i'$, then $c_i \neq c_{i'}$. Between any two towns, there is at most one road (including newly built roads).

Your program must output exactly one integer to standard output, which is the maximum obtainable revenue.

In the sample, $\text{Mr. Greedy}$ should set the toll of the new road $(1,3)$ to $5$ cents. With this toll, he can choose roads $(3,5), (1,2), (2,4), (1,3)$ to minimize the total toll, which is $14$. The $30$ people from town $3$ and the $50$ people from town $5$ will pass through the new road on their way to town $1$, so he can obtain the best revenue of $(30+50)×5=400$ cents. If instead we set the toll of the new road $(1,3)$ to $10$ cents, then by the customary constraint $\text{Mr. Greedy}$ must choose $(3,5), (1,2), (2,4), (2,3)$, because this is the unique set with minimum total toll. Therefore, during the carnival the road $(1,3)$ will bring no revenue. We will use the following $5$ types of test cases to evaluate your program. 1. (International $16$ points, Domestic $15$ points) $N \leq 10, M \leq 20, K = 1$. 2. (International $18$ points, Domestic $20$ points) $N \leq 30, M \leq 50, K \leq 10$. 3. (International $22$ points, Domestic $20$ points) $N \leq 10^3, M \leq 5 \times 10^3, K \leq 10$. 4. (International $22$ points, Domestic $20$ points) $N \leq 10^5, M \leq 3 \times 10^5, K \leq 15$. 5. (International $22$ points, Domestic $25$ points) $N \leq 10^5, M \leq 3 \times 10^5, K \leq 20$. update: 2024/07/04 Two test points were removed, and the tests were changed to bundled. Translated by ChatGPT 5