#P5304. P5304 [GXOI/GZOI2019] 旅行者
P5304 [GXOI/GZOI2019] 旅行者
P5304 [GXOI/GZOI2019] 旅行者
提高+/省选- | 来源:GXOI/GZOI2019 | 原题链接
题意
组数据。 座城市、 条有向道路(可能自环、重边), 个兴趣城市。求兴趣城市之间「两两最短路」的最小值(即最近一对的最短距离;有向, 或 任一可达即算)。保证至少一对兴趣城市互相连通。
输入格式
每个测试点包含多组数据,第一行是一个整数 ,表示数据组数。注意各组数据之间是互相独立的。
对于每组数据,第一行包含三个正整数 ,表示 J 国的 座城市(从 编号), 条道路,Vani 感兴趣的城市的个数 。
接下来 行,每行包括 个正整数 ,表示从第 号城市到第 号城市有一条长度为 的单向道路。注意 可能相等,一对 也可能重复出现。
接下来一行包括 个正整数,表示 Vani 感兴趣的城市的编号。数据保证这 座城市之间至少有一对城市是连通的。
输出格式
输出文件应包含 行,对于每组数据,输出一个整数表示 座城市之间两两最短路的最小值。
输入输出样例
样例 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
数据范围
,,,; 规模见下表:测试点 1–2 为 ;3–5 为 且保证有向无环;6–10 无限制。测试点五可能存在自环。
提示
考点:多源 Dijkstra + 随机分组。把 个兴趣点随机染成黑白两组,多源 Dijkstra 求每组到对组的最近距离,取最小;重复约 30 次,任意一对必然在某次被分进不同组。易错点:① 有向图,两个方向都要算(两次多源各算一遍);② 自环、重边照常处理即可;③ 可达 ,距离和要开 long long;④ 朴素对每对兴趣点跑 Dijkstra 是 次,过不了;本题随机化不保证正确性证明,但错误概率 。