题目内容

塔之国有$n$个城市，塔塔作为塔之国国王，他希望所有塔之国的城市能够连通起来。

现在他下令塔之国的所有施工队同时施工同时，已知塔之国的施工队的施工速度均为$1$距离单位/年，

对于每个城市，城市的领导者都会向每个相邻的城市派出施工队进行修路(所有城市相邻)，

并且每个施工队都按照最短的路线修路，如果两个施工队碰头，那么两个城市相连。

思路:最小生成树

按照题意由于数据只有1000，那么直接建造一个无向完全图，无向完全图的边数为$n*(n-1)/2$，要求图联通，直接跑最小生成树即可. $\\$ 整体时间复杂度$o(n^2*log_2n)$$\\$ 还有一个很好想到的思路，直接二分答案然后把符合的边加入到集合之中最后整体判断该图是不是联通图即可$\\$ 整体时间复杂度$o(n^2*{log_2}^2n)$ $\\$ 最小生成树->https://oi-wiki.org/graph/mst/

代码如下

$cpp$