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 翻译