莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 最终答案必定不会小于各个连通块的最大距离 res1
2. 计算出每个连通块中各个点能到达的最远距离
3. 枚举能连的点，距离就是两个点之间的距离 + 两个点在各自连通块能到达的最远距离，然后取最小值 res2
4. 最终答案就是 max(res1, res2)

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 160;
const double INF = 0x3f3f3f3f;

int n;
PII q[N];
char g[N][N];
double d[N][N],maxd[N];

//求解两点之间的直线距离
double get_dist(PII a,PII b)
{
    int dx=a.x-b.x,dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y;

    for(int i=0;i<n;i++) cin>>g[i];

    //两点之间有边就求距离
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j)
            {
                if(g[i][j]=='1') d[i][j]=get_dist(q[i],q[j]);
                else d[i][j]=INF;
            }

    //Floyd算法求两点之间最短路   
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)  
            for(int j=0;j<n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

    //求解一个连通块中距离 i 这个点的最远距离
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(d[i][j]<INF)
                maxd[i]=max(maxd[i],d[i][j]);

    //求解各个连通块中两点最远的距离
    double res1=0;
    for(int i=0;i<n;i++) res1=max(res1,maxd[i]);

    //求解各个连通块连一条边后最远的距离的最小值
    double res2=INF;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(d[i][j]==INF)
                res2=min(res2,maxd[i]+get_dist(q[i],q[j])+maxd[j]);

    //最终答案是两个值取最大值
    printf("%lf\n",max(res1,res2));

    return 0;
}