分数: 400 分
问题陈述
Takahashi 是数据中心的网络管理员, N 服务器。服务器编号从 1 to N.
有 M 用于连接服务器的可用电缆,电缆的编号也从 1 to M。的 i第电缆 (1 \leq i \leq M) 双向连接服务器 U_i 和服务器 V_i,安装成本为 W_i。每根电缆连接两个不同的服务器(即 U_i \neq V_i)。然而,可能有多条电缆连接同一对服务器。
高桥想要选择一些电缆来构建网络,以便所有 N 服务器可以相互通信。所选电缆组必须形成一个 生成树。生成树是一个包含所有 N 服务器作为顶点,其中所有服务器都通过选定的电缆连接,并且不存在循环(在这种情况下,恰好 选择 N-1 电缆)。
但是,由于安全要求,一组特定的 K 电缆(编号 E_1, E_2, \dots, E_K)已被签约为专用加密通信线路,并且必须包含在网络中。
如果存在包含所有 K 指定电缆,输出该电缆的最小总安装成本 N-1 电缆包含在该生成树中。如果不存在这样的生成树,则输出 -1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq K \leq N - 1
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i
- 1 \leq W_i \leq 10^9
- 1 \leq E_j \leq M (1 \leq j \leq K)
- 全部 E_j 是不同的
- 所有输入值均为整数
输入
N M K U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M E_1 E_2 \dots E_K
- 第一行包含服务器数量 N,可用电缆的数量 M,以及必须包含的电缆数量 K,用空格分隔。
- 从第 2 行到 (M + 1)第行,给出每根电缆的信息 M 行。
- 的 (1 + i)第行表示 i-th 电缆连接服务器 U_i 和服务器 V_i 安装成本为 W_i.
- If K \geq 1, (M + 2)- 第行包含电缆编号 E_1, E_2, \dots, E_K 必须包含在网络中,并用空格分隔。如果 K = 0,该行不存在。
输出
如果存在包含所有 K 指定电缆,在一根线上输出该电缆的最小总安装成本 N-1 电缆包含在该生成树中。如果不存在这样的生成树,则输出 -1.
示例输入 1
4 5 1 1 2 3 2 3 1 1 3 2 3 4 4 2 4 5 1
示例输出 1
8
示例输入 2
3 3 2 1 2 1 1 2 2 2 3 3 1 2
示例输出 2
-1
示例输入 3
8 12 2 1 2 5 2 3 3 3 4 7 4 5 2 5 6 8 6 7 4 7 8 6 1 3 9 2 5 1 4 7 10 1 8 11 3 6 12 2 6
示例输出 3
29
示例输入 4
10 15 3 1 2 10 2 3 20 3 4 5 4 5 15 5 6 8 6 7 12 7 8 3 8 9 7 9 10 11 1 5 25 2 6 18 3 7 6 4 8 14 5 9 9 1 10 30 3 8 14
示例输出 4
77
示例输入 5
2 1 0 1 2 1000000000
示例输出 5
1000000000