POJ 2253 Frogger(Floyd)

(￣▽￣)"

//             （        ）     （  minimax），
//  frog distance，
//        ，
//          folyd  ，
//folyd                ；
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double lowcost[210][210];

struct xy
{
    int x,y;
}s[210];

void floyd(int n)
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(lowcost[i][j]>lowcost[i][k]&&lowcost[i][j]>lowcost[k][j])
                    lowcost[i][j]=lowcost[j][i]=max(lowcost[i][k],lowcost[k][j]);
}

double dis(int a,int b)
{
    return sqrt((double)(s[a].x-s[b].x)*(s[a].x-s[b].x)+(double)(s[a].y-s[b].y)*(s[a].y-s[b].y));
}

int main()
{
    int n,Case=0;
    while(scanf("%d",&n)&&n!=0)
    {
        Case++;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                lowcost[i][j]=10000000;
        for(int i=1;i<=n;i++)
            scanf("%d%d",&s[i].x,&s[i].y);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                lowcost[i][j]=lowcost[j][i]=dis(i,j);
        floyd(n);
        printf("Scenario #%d
Frog Distance = %.3lf

",Case,lowcost[1][2]);
    }
    return 0;
}