分数: 500 点
问题陈述
给你一个简单的连通无向图 N 顶点和 M 边,其中顶点已编号 1 to N 和边已编号 1 to M。边缘 i (1 \leq i \leq M) 连接顶点 u_i 和 v_i 双向且有重量 w_i.
对于路径,将其权重定义为路径中边的最大权重。 定义 f(x, y) 作为从顶点开始的路径的最小可能路径权重 x 到顶点 y.
给定两个长度的序列 K: (A_1, A_2, \ldots, A_K) 和 (B_1, B_2, \ldots, B_K)。可以保证 A_i \neq B_j (1 \leq i,j \leq K).
排列序列 B 自由地这样 \displaystyle \sum_{i=1}^{K} f(A_i, B_i) 被最小化。
约束
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5)
- 1 \leq K \leq N
- 1 \leq u_i<v_i \leq N (1 \leq i \leq M)
- 1 \leq w_i \leq 10^9
- 1 \leq A_i,B_i \leq N (1 \leq i \leq K)
- 给定的图很简单且连通。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M K u_1 v_1 w_1 u_2 v_2 w_2 \vdots u_M v_M w_M A_1 A_2 \ldots A_K B_1 B_2 \ldots B_K
输出
打印最小值 \displaystyle \sum_{i=1}^{K} f(A_i, B_i).
示例输入 1
4 4 3 1 3 2 3 4 1 2 4 5 1 4 4 1 1 3 4 4 2
示例输出 1
8
如果我们重新排列 B as (2,4,4):
- f(1,2) = 5:从顶点开始的路径 1 到顶点 2 穿过顶点 4 包含边缘 3 最大边权重为 5。不存在最大边权重小于或等于的路径 4,所以 5 是可能的最小值。
- f(1,4) = 2:从顶点开始的路径 1 到顶点 4 穿过顶点 3 包含边缘 1 最大边权重为 2。不存在最大边权重小于或等于的路径 1,所以 2 是可能的最小值。
- f(3,4) = 1:从顶点开始的路径 3 到顶点 4 穿过直接边包含最大边权重为 1。没有路径可以有最大权重 0 或更少,所以 1 是可能的最小值。
因此, \displaystyle \sum_{i=1}^{3} f(A_i, B_i) = 5+2+1=8。没有排列 B 产量 7 或更少,所以答案是 8.
示例输入 2
3 3 2 1 2 5 2 3 2 1 3 1 1 1 2 3
示例输出 2
3