rt,并查集+floyd

#include<bits/stdc++.h>
using namespace std;
const int N = 155,M = N*N;
int n;
struct node{
    int x,y;
}a[N];
double get_dis(int x,int y){
    node p1 = a[x],p2 = a[y];
    double k = (double)(p1.x-p2.x)*(p1.x-p2.x) + (double)(p1.y-p2.y)*(p1.y-p2.y);
    return sqrt(k);
}
double g[N][N],far[N],o[N];
void floyd(){
    for(int k = 1;k <= n;k ++)
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                g[i][j] = max(g[i][j],g[i][k]+g[k][j]);
    return ;
}
int fa[N];
int find(int x){
    if(fa[x] == x || fa[x] == 0)
        return fa[x] = x;
    return fa[x] = find(fa[x]);
}
void merge(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy) fa[fx] = fy;
    return ;
}
void get_far(){
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n;j ++)
            if(find(i) == find(j)) far[i] = max(far[i],g[i][j]);
        o[find(i)] = max(o[find(i)],far[i]);
    }
    return ;
}
signed main(){
    cin >> n;
    for(int i = 1;i <= n;i ++)
        cin >> a[i].x >> a[i].y;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++){
            char c;
            cin >> c;
            if(i == j) g[i][j] = 0;
            else if(c == '0') g[i][j] = 1 << 30;
            else{
                g[i][j] = get_dis(i,j);    
                merge(i,j);
            }
        }
    floyd();
    get_far();
    double ans = 1 << 30;
    for(int i = 1;i <= n;i ++)
        for(int j = i+1;j <= n;j ++)
            if(find(i) != find(j))
                ans = min(ans,
                max(
                    far[i]+far[j]+get_dis(i,j),
                    max(o[find(i)],o[find(j)]))
                );
    printf("%.6f",ans);
    return 0;
}