[APIO2013] 道路费用
题目描述
幸福国度可以用 N 个城镇（用 1 到 N 编号）构成的集合来描述，这些城镇 最开始由 M 条双向道路（用 1 到 M 编号）连接。城镇 1 是中央城镇。保证一个 人从城镇 1 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是 收费道路，道路 i 的使用者必须向道路的主人支付 ci分钱的费用。已知所有的这 些ci是互不相等的。最近有K条新道路建成，这些道路都属于亿万富豪Mr. Greedy。 Mr. Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣 布这些费用。
两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这 些道路游行并前往中央城镇。共计 pj个参与者将从城镇 j 出发前往中央城镇。这 些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一 天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就 是 Mr. Greedy。同样根据这个习俗，Mr. Greedy 选出的这个道路集合必须使所有 选出道路的费用之和最小，并且仍要保证任何人可以从城镇 j 前往城镇 1（因此， 这些选出的道路来自将费用作为相应边边权的“最小生成树”）。如果有多个这样 的道路集合，Mr. Greedy 可以选其中的任何一个，只要满足费用和是最小的。
Mr. Greedy 很明确地知道，他从 K 条新道路中获得的收入不只是与费用有 关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 p 个人经过道路 i，道路 i 产生的收入为 ci p 的积。注意 Mr. Greedy 只能从新道路 收取费用，因为原来的道路都不属于他。
Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收 入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路 （将在嘉年华的前一天公布），使得他在 K 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。
你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序 来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。
输入格式
你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数 N，M 和 K。接下来的 M 行描述最开始的 M 条道路。这 M 行中的第 i 行包含由空格隔开 的整数 ai，bi和 ci，表示有一条在 ai 和 bi之间，费用为 ci 的双向道路。接下来的 K 行描述新建的 K 条道路。这 K 行中的第 i 行包含由空格隔开的整数 xi和 yi，表 示有一条连接城镇 xi 和 yi 新道路。最后一行包含 N 个由空格隔开的整数，其中 的第 j 个为 pj，表示从城镇 j 前往城镇 1 的人数。
输入也满足以下约束条件。
1 ≤ N ≤ 100000；
1 ≤ K ≤ 20；
1 ≤ M ≤ 300000；
对每个 i 和 j，1 ≤ ci, pj ≤ 10^6；
如果 i ≠ i'，则 ci ≠ ci'；
在任意两个城市之间，最多只有一条道路（包括新建的道路）。
输出格式
你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。
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
400
提示
在样例中，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 分钱。根据传统的限制， Mr. Greedy 必须选择(3,5)，(1,2)，(2,4)和(2,3)，因为这是唯一费用最小的集合。 因此，在嘉年华的过程中道路(1,3)将没有任何收入。
我们将使用以下 5 类测例测试你的程序。
-
（国际 16 分，国内 15 分）N ≤ 10，M ≤ 20 且 K = 1；
-
（国际 18 分，国内 20 分）N ≤ 30，M ≤ 50 且 K ≤ 10；
-
（国际 22 分，国内 20 分）N ≤ 1,000，M ≤ 5,000 且 K ≤ 10；
-
（国际 22 分，国内 20 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 15；
-
（国际 22 分，国内 25 分）N ≤ 100,000，M ≤ 300,000 且 K ≤ 20。
update: 2024/07/04 删除了两个测试点，并且改为捆绑。