33OJ
登录 注册

#CF2014E. 玛丽安与罗宾的会面 / Rendez‑vous de Marian et Robin

玛丽安与罗宾的会面 / Rendez‑vous de Marian et Robin

题目描述

交通网络由 nn 个编号 1∼n1\sim n 的顶点与 mm 条边构成。第 ii 条边连接顶点 uiu_i 和 viv_i,通行耗时 wiw_i 秒(所有 wiw_i 均为偶数)。玛丽安从顶点 11(集市)出发,罗宾从顶点 nn(大橡树)出发。

另外,nn 个顶点中有 hh 个顶点各有一匹马。玛丽安和罗宾都会骑马,上马不需要耗费时间(0 秒)。骑马时通行时间减半。一旦骑上马,之后全程都处于骑马状态。两人必须在某个顶点碰面,不能在边上相遇。任意一人都可以选择在某个顶点原地等待。

求玛丽安与罗宾能够碰面的最早时刻。如果顶点 11 和 nn 不连通,则会面取消,输出 −1-1。

输入格式

第一行一个整数 tt(1≤t≤1041\le t \le 10^4),代表测试用例数量。

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

第二行包含 hh 个互不相同的整数 a1,a2,…,aha_1,a_2,\ldots,a_h(1≤ai≤n1 \le a_i \le n)——拥有马匹的顶点编号。

接下来 mm 行,每行三个整数 ui,vi,wiu_i,v_i,w_i(1≤ui,vi≤n,  2≤wi≤1061\le u_i,v_i \le n,\;2\le w_i \le 10^6),代表 uiu_i 与 viv_i 之间有一条边,不骑马通过这条边需要 wiw_i 秒。

图不存在自环与重边。保证所有 wiw_i 均为偶数。

保证全部测试用例的 nn 之和、mm 之和均不超过 2⋅1052\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
5
-1
6
19
14
12

说明

第一个测试用例:玛丽安骑马从顶点 11 走到顶点 22,罗宾原地等待。

第二个测试用例:顶点 11 和顶点 33 之间不连通。

第三个测试用例:玛丽安与罗宾都前往顶点 22 完成会面。

第四个测试用例:玛丽安不骑马走到顶点 22,在顶点 22 骑上马,骑马走到顶点 33,与罗宾碰面。

第五个测试用例:玛丽安不骑马走到顶点 22,骑上马后返回顶点 11,再前往顶点 33;罗宾原地等待。

原题链接

原题链接