题目背景

点我进入原题提交页面

题目描述

给你一个简单相连的无向图，图中有 $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$

接下来 $M$ 行每行三个整数分别为 $u_i,v_i,w_i$

接下来一行输入 $K$ 个空格隔开的证书代表序列 $A$

接下来一行输入 $K$ 个空格隔开的证书代表序列 $B$

输出格式

输出题目所求

4 4 3
1 3 2
3 4 1
2 4 5
1 4 4
1 1 3
4 4 2

8

3 3 2
1 2 5
2 3 2
1 3 1
1 1
2 3

3

提示

数据范围

• $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$ 重排为 $(2,4,4)$，接下来

• $f(1,2)=5$
• $f(1,4)=2$
• $f(3,4)=1$

因此答案为 $5+2+1=8$ 可以证明不存在更小的答案。