#P5304. P5304 [GXOI/GZOI2019] 旅行者

P5304 [GXOI/GZOI2019] 旅行者

P5304 [GXOI/GZOI2019] 旅行者

提高+/省选- | 来源:GXOI/GZOI2019 | 原题链接

题意

TT 组数据。nn 座城市、mm 条有向道路(可能自环、重边),kk 个兴趣城市。求兴趣城市之间「两两最短路」的最小值(即最近一对的最短距离;有向,i→ji\to j 或 j→ij\to i 任一可达即算)。保证至少一对兴趣城市互相连通。

输入格式

每个测试点包含多组数据,第一行是一个整数 TT,表示数据组数。注意各组数据之间是互相独立的。

对于每组数据,第一行包含三个正整数 n,m,kn,m,k,表示 J 国的 nn 座城市(从 1∼n1 \sim n 编号),mm 条道路,Vani 感兴趣的城市的个数 kk。

接下来 mm 行,每行包括 33 个正整数 x,y,zx,y,z,表示从第 xx 号城市到第 yy 号城市有一条长度为 zz 的单向道路。注意 x,yx,y 可能相等,一对 x,yx,y 也可能重复出现。

接下来一行包括 kk 个正整数,表示 Vani 感兴趣的城市的编号。数据保证这 kk 座城市之间至少有一对城市是连通的。

输出格式

输出文件应包含 TT 行,对于每组数据,输出一个整数表示 kk 座城市之间两两最短路的最小值。

输入输出样例

样例 1 输入

2
6 7 3
1 5 3
2 3 5
1 4 3
5 3 2
4 6 5
4 3 7
5 6 4
1 3 6
7 7 4
5 3 10
6 2 7
1 2 6
5 4 2
4 3 4
1 7 3
7 2 4
1 2 5 3

样例 1 输出

5
6

数据范围

T≤5T\le 5,2≤k≤n≤1052\le k\le n\le 10^5,m≤5×105m\le 5\times10^5,1≤z≤2×1091\le z\le 2\times10^9;n,mn,m 规模见下表:测试点 1–2 为 n≤1000,m≤5000n\le1000,m\le5000;3–5 为 n≤105,m≤5×105n\le10^5,m\le5\times10^5 且保证有向无环;6–10 无限制。测试点五可能存在自环。

提示

考点:多源 Dijkstra + 随机分组。把 kk 个兴趣点随机染成黑白两组,多源 Dijkstra 求每组到对组的最近距离,取最小;重复约 30 次,任意一对必然在某次被分进不同组。易错点:① 有向图,两个方向都要算(两次多源各算一遍);② 自环、重边照常处理即可;③ zz 可达 2×1092\times10^9,距离和要开 long long;④ 朴素对每对兴趣点跑 Dijkstra 是 O(k2)O(k^2) 次,过不了;本题随机化不保证正确性证明,但错误概率 ≈(1/2)30\approx (1/2)^{30}。

蜀ICP备2025119001号-1