[QBXT图论欢乐赛]潜伏

[QBXT图论欢乐赛]潜伏

题目背景

小悠回家之后,跟着母亲看了很多抗日神剧,其中不乏一些谍战片。

题目描述

解放前夕,北平城内潜伏着若干名地下党员,他们居住在城市的不同位置。现在身为地下党第一指挥官的你,想知道地下党员之间的最小通信距离,即从某一地下党员住处前往另一地下党员住处的距离的最小值我们可以将北平城视为一张\(N\)个点\(M\)条边的无向图,每条边连接两个点\( u_1,v_1 \),且长度为\( wi \)。

输入格式

每个测试点包含多组数据。
第一行,给出数据组数\( T \),之后依次输入毎组数据。
每组数据的第一行,\( N,M,K \),分别表示点数,边数,地下党员数。
之后\( M \)行,每行\( u_i,v_i,w_i \)表示第i条边。
之后一行,\( K \)个整数代表地下党员所在结点。
结点编号为\( 1 \)到\( N \),保证 \( N \ge K \)

输出格式

对于每组数据,输出一行一个整数,表示地下党员之间的最小通信距离。
如果最小通信距离为\(\infty\),请输出\(-1\)代替。

样例输入

3
5 10 3
1 3 437
1 2 282
1 5 328
1 2 519
1 2 990
2 3 837
2 4 267
2 3 502
3 5 613
4 5 132
1 3 4
10 13 4
1 6 484
1 3 342
2 3 695
2 3 791
2 8 974
3 9 526
4 9 584
4 7 550
5 9 914
6 7 444
6 8 779
6 10 350
8 8 394
9 10 3 7
10 9 4
1 2 330
1 3 374
1 6 194
2 4 395
2 5 970
2 10 117
3 8 209
4 9 253
5 7 864
8 5 10 6

样例输出

437
526
641

数据范围

对于所有测试点,\(T \le 10\),时间限制\(2000m\),内存限制\(1GB\)
对于50%的测试点,\(N<1000,M\le2000\)
对于20%的测试点,\(N<100000\)输入的无向图无环。
对于30%的测试点,\(N<100000,M \le 200000\)
所有\(0 \le w_i \le 1000\)。

信息

ID
1397
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
2
上传者