← 返回题目列表

AtCoder · asaporo2_a

A. 多彩MST

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

分数: 700 点

问题陈述

Ringo 有一个无向图 G 与 N 顶点编号 1,2,...,N 和 M 边编号 1,2,...,M。 边缘 i 连接顶点 a_{i} 和 b_{i} 的长度为 w_i.

现在,他正在画这些 N 中的顶点 K 颜色编号 1,2,...,K。顶点 i 已涂上颜色 c_i,除非 c_i = 0,在这种情况下顶点 i 尚未绘制。

在他绘制了其中一个尚未绘制的每个顶点之后 K 颜色,他会给 G 到 Snuke。

基于 G, Snuke 将制作另一个无向图 G' 与 K 顶点编号 1,2,...,K 和 M 边缘。 最初,没有任何优势 G'。的 i第一条边将添加如下:

  • 让 x 和 y 是由边连接的两个顶点的颜色 i in G.
  • 添加长度为 的边 w_i 连接顶点 x 和 y in G'.

的最小生成树中边的长度的最小可能总和是多少 G'?如果 G' 无论Ringo如何绘制顶点都不会连接,打印 -1.

约束

  • 1 \leq N,M \leq 10^{5}
  • 1 \leq K \leq N
  • 0 \leq c_i \leq K
  • 1 \leq a_i,b_i \leq N
  • 1 \leq w_i \leq 10^{9}
  • 给定的图形可能不是简单的或连通的。
  • 所有输入值均为整数。

部分分数

  • 在测试集中值得 100 点, N = K 和 c_i = i.
  • 在测试集中值得另一个 100 点, c_i \neq 0.
  • 在测试集中值得另一个 200 点, c_i = 0.

输入

输入由标准输入按以下格式给出:

N M K
c_1 c_2 ... c_{N}
a_1 b_1 w_1
:
a_M b_M w_M

输出

打印答案。


示例输入 1

4 3 3
1 0 1 2
1 2 10
2 3 20
2 4 50

示例输出 1

60

G' 仅当 Vertex 时才会连接 2 涂有颜色 3.


示例输入 2

5 2 4
0 0 0 0 0
1 2 10
2 3 10

示例输出 2

-1

无论 Ringo 如何绘制顶点,两条边都不足以将四个顶点连接为一个。


示例输入 3

9 12 9
1 2 3 4 5 6 7 8 9
6 9 9
8 9 6
6 7 85
9 5 545631016
2 1 321545
1 6 33562944
7 3 84946329
9 7 15926167
4 7 53386480
5 8 70476
4 6 4549
4 8 8

示例输出 3

118901402

示例输入 4

18 37 12
5 0 4 10 8 7 2 10 6 0 9 12 12 11 11 11 0 1
17 1 1
11 16 7575
11 15 9
10 10 289938980
5 10 17376
18 4 1866625
8 11 959154208
18 13 200
16 13 2
2 7 982223
12 12 9331
13 12 8861390
14 13 743
2 10 162440
2 4 981849
7 9 1
14 17 2800
2 7 7225452
3 7 85
5 17 4
2 13 1
10 3 45
1 15 973
14 7 56553306
16 17 70476
7 18 9
9 13 27911
18 14 7788322
11 11 8925
9 13 654295
2 10 9
10 1 545631016
3 4 5
17 12 1929
2 11 57
1 5 4
1 17 7807368

示例输出 4

171