USACOの第2章の最後の1題、ほほほ

/*
ID: morgan_xww
LANG: C
TASK: cowtour
*/

/**
        ：     (pasture)，   (x,y)   ，          ，
                       ，            (field)，     
                 ：                    。      
                ，                ，           
                  ，       。
      ：            ，    ，           (    )。
                  ，        。
         ：  Floyd               ，        ，    
                  ，           ，               pst[i].dis。
                    i,j,  i,j       ，            
                   ：i        ;j        ;pst[i].dis+distance(i,j)+pst[j].dis;
                          。                      ，
                               

**/

#include <stdio.h>
#include <math.h>

#define INF 10000000000.0

int    n;
int    fldNum;         //       
double map[151][151];
double fldDis[151];    //fldDis[i]  i      

struct COORD
{
    int    x, y;  //  
    int    fld;   //          
    double dis;   //      ，              
} pst[150];
   //        (pasture).

double Distance(struct COORD a, struct COORD b) //           
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void Floyd() //Floyd       
{
    int i, j, k;
    for (k=0; k<n; k++)
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                if (i != j && map[i][k]+map[k][j] < map[i][j])
                    map[i][j] = map[i][k]+map[k][j];
    return ;
}

double Max(double a, double b, double c) //      
{
    double t = (a > b ? a : b);
    return (t > c ? t : c);
}

int main()
{
    freopen("cowtour.in", "r", stdin);
    freopen("cowtour.out", "w", stdout);

    int  i, j, k;
    char c;
    double tmp, mindis;

    scanf("%d", &n);
    for (i=0; i<n; i++)
        scanf("%d %d", &pst[i].x, &pst[i].y);
    for (i=0; i<n; i++)
    {
        getchar();
        for (j=0; j<n; j++)
        {
            scanf("%c", &c);
            if ('0' == c)
                map[i][j] = INF+10.0;
            else
                map[i][j] = Distance(pst[i], pst[j]);
        }
    }
    Floyd();
             //                     
    for (i=0; i<n; i++)
    {
        pst[i].dis = 0.0;
        for (j=0; j<n; j++)
        {
            if (map[i][j]<INF && map[i][j]>pst[i].dis)
                pst[i].dis = map[i][j];
        }
    }
            //       ，          
    fldNum = 1;
    for (i=0; i<n; i++)
    {
        if (pst[i].fld > 0) continue;
        pst[i].fld = fldNum;
        tmp = pst[i].dis;
        for (j=i+1; j<n; j++)
        {
            if (map[i][j] < INF)
            {
                pst[j].fld = fldNum;
                if (pst[j].dis > tmp)
                    tmp = pst[j].dis;
            }
        }
        fldDis[fldNum] = tmp;
        fldNum++;
    }
             //                   
    mindis = INF;
    for (i=0; i<n; i++)
    {
        for (j=i+1; j<n; j++)
        {
            if (pst[i].fld == pst[j].fld) continue;  //           
            tmp = Distance(pst[i], pst[j])+pst[i].dis+pst[j].dis;
            tmp = Max(tmp, fldDis[pst[i].fld], fldDis[pst[j].fld]);
            if (tmp < mindis)
                mindis = tmp;
        }
    }
    printf("%.6lf/n", mindis);
    exit(0);
}