关于旅行者的近10条评论(全部评论)
┭┮﹏┭┮ 2023-11-14 19:03 6楼
数据太弱，建议加强数据生成器： `int T=5,n=5000,m=(n-1)2,k=n/10,len=10; printf("%d\n",T); while(T--){ printf("%d%d%d\n",n,m,k); for(int i=1;i<=k;++i){ int id=(i-1)len+1; if(id!=1){ printf("%d%d%d\n",1,id,1); printf("%d%d%d\n",id,1,1); } for(int j=id+1;j<id+len;++j){ printf("%d%d%d\n",j-1,j,1); printf("%d%d%d\n",j,j-1,1); } } for(int i=1;i<=k;++i){ printf("%d",i*len); } puts(""); }` ムラサメ 2023-11-14 14:27 5楼
回复 @Skylake 是初中有一次把咱叫去听高中的课的时候讲的，当时我听完大受震撼，以至于其他题都忘了就记着这一题hh op_组撒头屯 2022-10-26 21:38 4楼
回复 @组撒头屯 : 不记得了欸，可能我还没听吧，这题正解反而简单一点，次解更巧妙 yrtiop 2022-10-26 21:30 3楼
回复 @Skylake : 我记得好早之前的集训讲过这题，没记错应该是不停按二进制分两组跑最短路，不过具体分法也忘了 op_组撒头屯 2022-10-26 21:00 2楼
$\mathcal O(Tn\log n\log k)$ 的做法属实人类智慧，感觉比正解还巧妙 yrtiop 2022-10-26 20:57 1楼

3109. [GXOI/GZOI2019]旅行者

★★★☆ 输入文件：WAW.in 输出文件：WAW.out 简单对比
时间限制：4 s 内存限制：512 MiB

$SY$ 国有 $n$ 座城市，这些城市之间通过 $m$ 条单向道路相连，已知每条道路的长度。

一次，居住在 $SY$ 国的 $XB$ 邀请 $HS$ 来作客。不过，作为一名资深的旅行者，$HS$ 只对 $SY$ 国的 $k$ 座历史悠久、自然风景独特的城市感兴趣。

为了提升旅行的体验，$HS$ 想要知道他感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。

也许下面的剧情你已经猜到了——$HS$ 这几天还要忙着去其他地方游山玩水，就请你帮他解决这个问题吧。

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

对于每组数据，第一行包含三个正整数 $n,m,k$，表示 $SY$ 国的 $n$ 座城市（从 $1 \sim n$ 编号），$m$ 条道路，$HS$ 感兴趣的城市的个数 $k$。

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

接下来一行包括 $k$ 个正整数，表示 $HS$ 感兴趣的城市的编号。

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

5
6

点击下载样例2

对于第一组数据，$1$ 到 $3$ 最短路为 $5$；$1$ 到 $6$ 最短路为 $7$；$3,6$ 无法到达，所以最近的两点为 $1,3$，最近的距离为 $5$。

对于第二组数据，$1$ 到 $2$ 最短路为 $6$；$5$ 到 $3$ 最短路为 $6$；其余的点均无法互相达，所以最近的两点为 $1,2$ 和 $5,3$，最近的距离为 $6$。