← 返回题目列表

Codeforces · 2014/E

E. 玛丽安与罗宾的约会

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

缺席使心变得更亲近。罗宾在大橡树完成训练的同时,玛丽安在市场上卖掉了她的最后一件商品。他们迫不及待地想见面,于是两人都毫不拖延地出发了。

出行网络表示为从 $$$1$$$ 到 $$$n$$$ 编号的 $$$n$$$ 顶点和 $$$m$$$ 边。第 $$$i$$$ 条边连接顶点 $$$u_i$$$ 和 $$$v_i$$$,并需要 $$$w_i$$$ 秒来运行(所有 $$$w_i$$$ 都是偶数)。 Marian 从顶点 $$$1$$$(市场)开始,Robin 从顶点 $$$n$$$(Major Oak)开始。

此外,$$$n$$$ 个顶点中的 $$$h$$$ 每个都有一匹可用的马。玛丽安和罗宾都是熟练的骑手,可以立即上马(即 $$$0$$$ 秒内)。骑行时旅行时间减半。一旦上马,马就可以完成剩下的旅程。会议必须发生在顶点上(即不是在边上)。两者都可以选择在任何顶点等待。

输出Robin和Marian最早见面的时间。如果顶点 $$$1$$$ 和 $$$n$$$ 断开连接,则输出 $$$-1$$$,因为会议被取消。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行由三个整数组成 $$$n$$$, $$$m$$$, $$$h$$$ ($$$2 \le n \le 2 \cdot 10^5, \;1 \le m \le 2 \cdot 10^5, \; 1 \le h \le n$$$) — 顶点数、边数和数量具有一匹马的顶点。

每个测试用例的第二行包含 $$$h$$$ 不同的整数 $$$a_1, a_2, \ldots, a_h$$$ ($$$1 \le a_i \le n$$$) - 拥有一匹可用马的顶点。

然后跟随每个测试用例的 $$$m$$$ 行,每行包含三个整数 $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1\le u_i,v_i \le n, \; 2\le w_i \le 10^6$$$) - 意味着顶点之间有一条边$$$u_i$$$ 和 $$$v_i$$$ 加上没有马的旅行成本 $$$w_i$$$ 秒。

没有自环或多重边。幸运的是,所有 $$$w_i$$$ 都是偶数。

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

输出

对于每个测试用例,输出一个整数,罗宾和玛丽安最早见面的时间。如果他们不可能相遇,则输出$$$-1$$$。

示例

输入 #1

6
2 1 1
1
1 2 10
3 1 2
2 3
1 2 10
3 3 1
2
1 2 4
1 3 10
2 3 6
4 3 2
2 3
1 2 10
2 3 18
3 4 16
3 2 1
2
1 2 4
1 3 16
7 7 1
3
1 5 2
2 6 12
1 2 12
6 4 8
7 3 4
6 3 4
7 6 4

输出 #1

5
-1
6
19
14
12

注意

在第一个测试用例中,Marian 从顶点 $$$1$$$ 骑行到顶点 $$$2$$$,Robin 等待。

在第二个测试用例中,顶点 $$$1$$$ 和 $$$3$$$ 未连接。

在第三个测试用例中,Marian 和 Robin 都前往顶点 $$$2$$$ 见面。

在第四个测试用例中,Marian 在没有马的情况下前往顶点 $$$2$$$,在顶点 $$$2$$$ 上马,然后骑到顶点 $$$3$$$ 去见 Robin。

在第五个测试用例中,Marian 在没有马的情况下前往顶点 $$$2$$$,在顶点 $$$2$$$ 上马,骑回顶点 $$$1$$$,然后到达顶点 $$$3$$$。罗宾等待着。