← 返回题目列表

AtCoder · awc0080_d

D. 网络建设

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

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