#CF2014E. 玛丽安与罗宾的会面 / Rendez‑vous de Marian et Robin
玛丽安与罗宾的会面 / Rendez‑vous de Marian et Robin
题目描述
交通网络由 个编号 的顶点与 条边构成。第 条边连接顶点 和 ,通行耗时 秒(所有 均为偶数)。玛丽安从顶点 (集市)出发,罗宾从顶点 (大橡树)出发。
另外, 个顶点中有 个顶点各有一匹马。玛丽安和罗宾都会骑马,上马不需要耗费时间(0 秒)。骑马时通行时间减半。一旦骑上马,之后全程都处于骑马状态。两人必须在某个顶点碰面,不能在边上相遇。任意一人都可以选择在某个顶点原地等待。
求玛丽安与罗宾能够碰面的最早时刻。如果顶点 和 不连通,则会面取消,输出 。
输入格式
第一行一个整数 (),代表测试用例数量。
每组测试用例第一行三个整数 ($2 \le n \le 2\cdot 10^5,\;1 \le m \le 2\cdot 10^5,\;1 \le h \le n$)——顶点数、边数、拥有马匹的顶点数量。
第二行包含 个互不相同的整数 ()——拥有马匹的顶点编号。
接下来 行,每行三个整数 (),代表 与 之间有一条边,不骑马通过这条边需要 秒。
图不存在自环与重边。保证所有 均为偶数。
保证全部测试用例的 之和、 之和均不超过 。
输出格式
对每组测试用例输出一个整数,表示两人可以碰面的最早时刻。若无法碰面输出 。
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
说明
第一个测试用例:玛丽安骑马从顶点 走到顶点 ,罗宾原地等待。
第二个测试用例:顶点 和顶点 之间不连通。
第三个测试用例:玛丽安与罗宾都前往顶点 完成会面。
第四个测试用例:玛丽安不骑马走到顶点 ,在顶点 骑上马,骑马走到顶点 ,与罗宾碰面。
第五个测试用例:玛丽安不骑马走到顶点 ,骑上马后返回顶点 ,再前往顶点 ;罗宾原地等待。