【USACO 2.4】Cow Tours （最短路）

/*
TASK:cowtour
LANG:C++
*/
#include<cstdio>
#include<algorithm>
#include<cmath>
const double INF=0x3f3f3f3f;
using namespace std;
#define N 155
int n,x[N],y[N],b[N];
int color;
double ans;
double d[N][N];
double dis(int i,int j){return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}
void dfs(int x){
    b[x]=color;
    for(int i=1;i<=n;i++)
        if(d[x][i]!=INF&&!b[i])
            dfs(i);
}
int main(){
    freopen("cowtour.in","r",stdin);
    freopen("cowtour.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d ",&x[i],&y[i]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)d[i][j]=INF;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=n+1;j++){
        char c=getchar();
        if(c=='1')
            d[i][j]=dis(i,j);
    }
    for(int i=1;i<=n;i++)
        if(!b[i]){
            color++;
            dfs(i);
        }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)if(i!=j)
    if(d[i][j]>d[i][k]+d[k][j])
        d[i][j]=d[i][k]+d[k][j];


    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)if(d[i][j]!=INF)
        ans=max(ans,d[i][j]);
    double m=INF;

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)if(b[i]!=b[j]){
            double d1=0,d2=0;
            for(int k=1;k<=n;k++){
                if(d[i][k]!=INF)
                    d1=max(d1,d[i][k]);
                if(d[k][j]!=INF)
                    d2=max(d2,d[k][j]);
            }
            m=min(m,d1+d2+dis(i,j));
        }
    printf("%f\n",max(m,ans));
    return 0;
}