← 返回题目列表

Codeforces · 2222/F

F. 建筑树

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

我们谈谈吧(Tre Lune MMXIX)

Exber 有一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。第 $$$i$$$ 条边连接顶点 $$$u_i$$$ 和 $$$v_i$$$ 并具有权重 $$$w_i$$$。

对于每条路径,让其中边的权重组成一个集合$$$S$$$;那么该路径的长度定义为$$$\operatorname{mex}(S)$$$。这里,$$$\operatorname{mex}(S)$$$表示集合$$$S$$$的最小排除(MEX)$$$^{\text{*}}$$$。 设$$$\mathrm{dis}(u,v)$$$表示从$$$u$$$开始到$$$v$$$结束的所有路径中的最小路径长度。

现在,Exber 想要构造一个具有 $$$q$$$ 个顶点的新图。在新图中,第 $$$i$$$ 个顶点的颜色为 $$$c_i$$$。最初,该图中没有边。如果 Exber 添加一条连接顶点 $$$u$$$ 和顶点 $$$v$$$ 的边,则会花费 $$$\mathrm{dis}(c_u,c_v)$$$ 时间。如果给定图中顶点 $$$c_u$$$ 和顶点 $$$c_v$$$ 没有连接,Exber 无法在新图中添加连接顶点 $$$u$$$ 和顶点 $$$v$$$ 的边。

确定 Exber 连接新图所需花费的最短时间。

$$$^{\text{*}}$$$整数集合 $$$S_1, S_2, \ldots, S_k$$$ 的最小排除 (MEX) 被定义为集合 $$$S$$$ 中不出现的最小非负整数 $$$x$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1\le n,m\le 3\cdot 10^5$$$, $$$1\le q\le n$$$) — 分别是图中的节点数、图中的边数和新图中的节点数。

接下来的 $$$m$$$ 行每行包含三个整数 $$$u$$$、$$$v$$$ 和 $$$w$$$ ($$$1\le u,v\le n$$$, $$$0\le w\le m$$$),表示顶点 $$$u$$$ 和$$$v$$$。

下一行包含$$$q$$$整数$$$c_i$$$ ($$$1\le c_i\le n$$$),表示新图中顶点$$$i$$$的颜色为$$$c_i$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$3\cdot 10^5$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$3\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - Exber 连接新图所需花费的最短时间。如果不可能,则输出$$$-1$$$。

示例

输入
复制

4
5 6 3
1 2 0
2 3 1
3 4 2
3 5 1
5 1 0
4 5 1
1 2 4
10 12 5
7 2 3
5 8 0
8 9 2
1 8 1
3 5 0
10 6 0
7 4 3
1 10 0
3 1 0
1 7 2
2 9 0
6 8 0
3 5 9 10 6
10 12 5
8 2 0
10 1 1
6 10 0
4 2 3
4 3 2
3 8 3
10 7 0
4 5 1
6 4 0
2 10 0
1 3 0
7 9 0
6 1 7 9 5
5 4 2
5 1 0
5 2 0
1 2 1
3 4 2
1 3

输出
复制

1
4
5
-1

注意

在第一个测试用例中,原始图有 $$$5$$$ 个顶点和 $$$5$$$ 个边。新图中顶点的颜色为 $$$1$$$、$$$2$$$ 和 $$$4$$$。

第一个测试用例的原始图。括号内的数字表示新图中顶点的索引,其颜色是该顶点在原图中的索引。

在新图中,Exber 将添加边 $$$(1,2)$$$ 和 $$$(2,3)$$$,第一个边将花费他 $$$1$$$ 时间,第二个边将花费他 $$$0$$$ 时间;因此,总时间为 $$$1$$$。

在第二个测试用例中,原始图有 $$$10$$$ 个顶点和 $$$12$$$ 个边。新图中顶点的颜色为 $$$3$$$、$$$5$$$、$$$9$$$、$$$10$$$ 和 $$$6$$$。

第二个测试用例的原始图。括号内的数字表示新图中顶点的索引,其颜色是该顶点在原图中的索引。

在新图中,Exber 将添加边 $$$(1,2)$$$、$$$(2,3)$$$、$$$(3,4)$$$ 和 $$$(4,5)$$$,每条边将花费他 $$$1$$$ 时间;因此,总时间为 $$$4$$$。