---

借鉴大佬的思路，真跪了https://blog.csdn.net/qq_33890670/article/details/79703197

https://www.nowcoder.com/practice/a29d0b5eb46b4b90bfa22aa98cf5ff17?tpId=62&tqId=29464&tPage=1&ru=/kaoyan/retest/2002&qru=/ta/sju-kaoyan/question-ranking

本题核心：第k条路径的长度为2^K，则第k条路径的长度会大于前k-1条路径的总和。

由此我们可以推断：

（1）在添加第k条路径时，如果路径k连接的两个城市A 、B已经通过其他路径间接的连通了，那么第k条路径绝对不是AB间的最短路径（第k条路径之后的路径也不可能有比当前AB路径更短的路径了，因为第k条路径的长度会大于前k-1条路径的总和）

（2）在添加第k条路径时，如果路径k连接的两个城市A 、B是第一次被连通了（也就是说此前没有任何路径能连通AB，包括通过多条路径间接连通），那么路径k就是AB之间的最短距离了，因为以后不可能存在更短的路径连接AB，以后的单条路径只会越来越长。

 

由此，我们可以建立一个最小生成树MST，算出0号结点到其他结点的距离

 

1.构造一个并查集Tree[]，每个城市指向自己(结点值为-1)，二维数组dis记录城市之间的距离，初始化为-1不可达，dis[i][i]初始化为0

2.取第一条路径，第一条路径连接了城市a、b，城市a、b间最短路径就是第一条路径，然后把a、b合并在一个集合里

3.再取一条路径，分以下两种情况：

3.1如果这条边连接的城市c、d，已经在同一个集合里了（即已经联通了），那么当前的路径一定不是cd之间的最短路径了，忽略即可，继续看下一条路径。

3.2如果这条路径连接的城市c、d不在同一个集合里（之前没有联通过），这条路径是cd之间的最短路径；除此之外我们还可以看看通过这条路径能不能让c集合里的城市到d集合里的城市之间的路径更短，即是不是d[i][j]>(d[i][C]+dist+d[D][j]) ?(注意i和C一个集合，D和j一个集合)，如果是...