AT_abc383_e.[ABC383E] Sum of Max Matching

给定一个有 $N$ 个顶点、$M$ 条边的带权无向连通简单图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $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)$。

输入按以下格式从标准输入读入。

$ 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)$ 的最小值。

限制条件

• $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)$
• $A_i \neq B_j\ (1 \leq i, j \leq K)$
• 给定的图是简单且连通的
• 所有输入均为整数

样例解释 1

将 $B$ 重排为 $B=(2,4,4)$ 时，

• $f(1,2)=5$：存在一条从顶点 $1$ 经顶点 $4$ 到顶点 $2$ 的路径，其中第 $3$ 条边的权值为 $5$，这是路径上的最大权值。不存在最大权值小于等于 $4$ 的路径，因此 $5$ 是最小值。
• $f(1,4)=2$：存在一条从顶点 $1$ 经顶点 $3$ 到顶点 $4$ 的路径，其中第 $1$ 条边的权值为 $2$，这是路径上的最大权值。不存在最大权值小于等于 $1$ 的路径，因此 $2$ 是最小值。
• $f(3,4)=1$：存在一条从顶点 $3$ 到顶点 $4$ 的边，权值为 $1$，这是路径上的最大权值。路径权值不会小于 $1$，因此 $1$ 是最小值。

因此，此时 $\displaystyle\sum_{i=1}^{3}f(A_i,B_i)=5+2+1=8$。无论如何重排 $B$，都无法使和小于 $8$，所以答案为 $8$。

由 ChatGPT 4.1 翻译