[APIO2013] 道路费用

题目描述

幸福国度可以用 $N$ 个城镇（用 $1$ 到 $N$ 编号）构成的集合来描述，这些城镇 最开始由 $M$ 条双向道路（用 $1$ 到 $M$ 编号）连接。城镇 $1$ 是中央城镇。保证一个人从城镇 $1$ 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是收费道路，道路 $i$ 的使用者必须向道路的主人支付 $c_i$ 分钱的费用。已知所有的这些 $c_i$ 是互不相等的。最近有 $K$ 条新道路建成，这些道路都属于亿万富豪 $\text{Mr. Greedy}$。$\text{Mr. Greedy}$ 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣布这些费用。

两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这些道路前往中央城镇。共计 $p_j$ 个参与者将从城镇 $j$ 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就是 $\text{Mr. Greedy}$。同样根据这个习俗，$\text{Mr. Greedy}$ 选出的这个道路集合必须使所有选出道路的费用之和最小，并且仍要保证任何人可以从城镇 $j$ 前往城镇 $1$（因此， 这些选出的道路来自将费用作为相应边边权的“最小生成树”）。如果有多个这样的道路集合，$\text{Mr. Greedy}$ 可以选其中的任何一个，只要满足费用和是最小的。

$\text{Mr. Greedy}$ 很明确地知道，他从 $K$ 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 $p$ 个人经过道路 $i$，道路 $i$ 产生的收入为 $c_i \times p$ 的积。注意 $\text{Mr. Greedy}$ 只能从新道路收取费用，因为原来的道路都不属于他。

$\text{Mr. Greedy}$ 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路（将在嘉年华的前一天公布），使得他在 $K$ 条新道路的收入最大。注意 $\text{Mr. Greedy}$ 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序来确定 $\text{Mr. Greedy}$ 可以通过他的阴谋获取多少收入。

输入格式

你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数 $N,M,K$。接下来的 $M$ 行描述最开始的 $M$ 条道路。这 $M$ 行中的第 $i$ 行包含由空格隔开的整数 $a_i,b_i,c_i$，表示有一条在 $a_i$ 和 $b_i$ 之间，费用为 $c_i$ 的双向道路。接下来的 $K$ 行描述新建的 $K$ 条道路。这 $K$ 行中的第 $i$ 行包含由空格隔开的整数 $x_i$ 和 $y_i$，表示有一条连接城镇 $x_i$ 和 $y_i$ 的新道路。最后一行包含 $N$ 个由空格隔开的整数，其中的第 $j$ 个为 $p_j$，表示从城镇 $j$ 前往城镇 $1$ 的人数。

输入也满足以下约束条件：$1 \leq N \leq 10^5,1 \leq K \leq 20,1 \leq M \leq 3\times 10^5$，对每个 $i$ 和 $j$，$1 \leq c_i,p_j \leq 10^6$，如果 $i \neq i'$，则 $c_i \neq c_{i'}$；

在任意两个城市之间，最多只有一条道路（包括新建的道路）。

输出格式

你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。

输入输出样例

输入样例 #1

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

输出样例 #1

400

说明/提示

在样例中，$\text{Mr. Greedy}$ 应该将新道路 $(1,3)$ 的费用设置为 $5$ 分钱。在这个费用下，他可以选择道路 $(3,5),(1,2),(2,4),(1,3)$ 来最小化总费用，这个费用为 $14$。 从城镇 $3$ 出发的 $30$ 个人和从城镇 $5$ 出发的 $50$ 个人将经过新道路前往城镇 $1$，因此他可以获得为 $(30+50)×5=400$ 分钱的最好收入。

如果我们这样做，将新道路 $(1,3)$ 的费用设置为 $10$ 分钱。根据传统的限制，$\text{Mr. Greedy}$ 必须选择 $(3,5),(1,2),(2,4),(2,3)$，因为这是唯一费用最小的集合。 因此，在嘉年华的过程中道路 $(1,3)$ 将没有任何收入。

我们将使用以下 $5$ 类测例测试你的程序。

1. （国际 $16$ 分，国内 $15$ 分）$N ≤ 10,M ≤ 20,K = 1$；

2. （国际 $18$ 分，国内 $20$ 分）$N ≤ 30,M ≤ 50, K ≤ 10$；

3. （国际 $22$ 分，国内 $20$ 分）$N ≤ 10^3,M ≤ 5\times 10^3,K ≤ 10$;

4. （国际 $22$ 分，国内 $20$ 分）$N ≤ 10^5,M ≤ 3\times 10^5, K ≤ 15$；

5. （国际 $22$ 分，国内 $25$ 分）$N ≤ 10^5，M ≤ 3\times 10^5, K ≤ 20$。

update: 2024/07/04 删除了两个测试点，并且改为捆绑。