← 返回题目列表

AtCoder · abc383_e

H. 最大匹配总和

中文机器翻译题面 查看原题

分数: 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