[USACO] 2-4-3 Cow Tours

/*
ID: 551100k1
LANG: C++
TASK: cowtour
*/
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
struct P{
    double x,y;
    friend double operator * (P a,P b){
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
}d[155];
vector<int> s[155];
int v[155]={0},team[155],add=0;
double len[155]={0},R[155]={0},ma[155][155],ans=1e8,p;
void dfs_team(int k){
    team[k]=add;
    for(int i=0;i<s[k].size();i++)
        if(v[s[k][i]]==0)
            v[s[k][i]]=1,dfs_team(s[k][i]);
}
int main(){
    freopen("cowtour.in","r",stdin);
    freopen("cowtour.out","w",stdout);
    int n,i,j,k,x;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%lf %lf",&d[i].x,&d[i].y);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            scanf("%1d",&x);
            if(x){
                ma[i][j]=d[i]*d[j];
                s[i].push_back(j);
            }
            else ma[i][j]=1e8;
        }
    }
    for(k=0;k<n;k++)
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(i!=j && j!=k && i!=k && ma[i][k]!=0 && ma[k][j]!=0 && ma[i][k]+ma[k][j]<ma[i][j])
                    ma[i][j]=ma[i][k]+ma[k][j];
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(ma[i][j]!=1e8 && ma[i][j]>len[i]) len[i]=ma[i][j];
    for(i=0;i<n;i++)
        if(v[i]==0)
            v[i]=1,dfs_team(i),add++;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i!=j && team[i]==team[j] && ma[i][j]!=1e8 && ma[i][j]>R[team[i]])
                R[team[i]]=ma[i][j];
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i!=j && team[i]!=team[j]){
                p=max(R[team[i]],R[team[j]]);
                p=max(p,len[i]+len[j]+d[i]*d[j]);
                if(p<ans)
                    ans=p;
            }

    printf("%lf\n",ans);
}