【解题思路】
题目中直接给了邻接矩阵，那我们也用邻接矩阵存储边信息，这样比较方便。
1. 求图中任意两顶点间的最短路径长度
题中顶点数量N最大为150，可以运行复杂度为O ( V ^3 )的Floyd算法。输入后，对整个图跑一遍Floyd算法，得到任意两点间的最短路径长度。
2. 遍历每个点，m[i] 用于存储每个点到其他点的最长距离。
2. 任选两个连通分量进行连线，新的连通分量中任意两顶点间最短路径长度的最大值
设该图有m个连通分量。从中任选两个连通分量A与B。确定要连接A、B两个连通分量后，对于其中一种方案，在A中的顶点va与B中的顶点vb连接一条边，这条边记为eb，连通分量A与B合并为连通分量C。边eb一定是连通分量C的桥。
思考连通分量C之中，任意两点间最短路径，可能有3类情况：
- 子图A中两顶点间的路径，只经过A中顶点
- 子图B中两顶点间的路径，只经过B中顶点
- A中一个顶点到B中一个顶点，必定经过桥eb。
A中两顶点间、B中两定点间的最短路径已经通过跑Floyd算法得到了。第1、2种情况下最短路径长度的最大值都容易求。
对于第3种情况，设A中某顶点为x，B中某顶点为y，因为一定会经过桥eb，那么从x到y的最短路径一定是：x->va->vb->y。其最短路径距离为：x到va的最短路径长度+eb权值+vb到y的最短路径长度。
那么要找到A中某顶点到B中某顶点的最短路径的最大值，就是先在A中找到va最短路径长度最大的顶点x，再在B中找 到vb最短路径长度最大的顶点y，那么这样的x和y间的最短路径长度就是第3种情况下两顶点间最短路径长度的最大值。
对3种情况下的两顶点间最短路径长度的最大值取一个最大值，得到这个连通分量C的直径。
4. 得出结果
求出每种连线方案得到的新的连通分量的直径，求最小值
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int zb[155][2];
double dist[155][155],m[155];
int n;
double dis(int x,int y){
return sqrt((zb[x][0]-zb[y][0])*(zb[x][0]-zb[y][0])+(zb[x][1]-zb[y][1])*(zb[x][1]-zb[y][1]));
}
void Floyd(){//搜索路径
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i!=j)&&(i!=k)&&(j!=k)&&(dist[i][k]<1e10)&&(dist[k][j]<1e10)&&(dist[i][j]>dist[i][k]+dist[k][j]))
dist[i][j]=dist[i][k]+dist[k][j];
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>zb[i][0]>>zb[i][1];
char c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>c;
if(c=='1')
dist[i][j]=dis(i,j);
else dist[i][j]=1e10;
}
Floyd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dist[i][j]<1e10&&m[i]<dist[i][j]) m[i]=dist[i][j];
double minx=1e20,t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j && dist[i][j]==1e10){
t=dis(i,j);
if(minx>m[i]+m[j]+t)minx=m[i]+m[j]+t;
}
for(int i=1;i<=n;i++) minx=max(minx,m[i]);
printf("%.6lf",minx);
return 0;
}
