10803 - Thunder Mountain

#include<iostream>
#include<cmath>
#include<cstdio>
#define INF 1e+8
#define MX 105
using namespace std;

struct City
{
    int x,y;
}city[MX];

double W[MX][MX];
double Floyed(int);
double MIN(double,double);

int main()
{
    register int t,c,i,j,n,x,y;
    double dis;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);

    for(c=1;c<=t;c++)
    {
        scanf("%d",&n);

        for(i=0;i<n;i++)
        {
            W[i][i] = 0;
            scanf("%d%d",&city[i].x ,&city[i].y);
        }

        for(i=0;i<n;i++)
        {
            for(j=0;j<i;j++)
            {
                x = city[i].x - city[j].x;
                y = city[i].y - city[j].y;

                x = x*x+y*y;
                if(x<=100)
                    W[i][j] = W[j][i] = sqrt(x);
                else
                    W[i][j] = W[j][i] = INF;
            }
        }
        dis = Floyed(n);
        if(dis==INF)
            printf("Case #%d:\nSend Kurdy\n\n",c);
        else
            printf("Case #%d:\n%0.4lf\n\n",c,dis);
    }
    return 0;
}

double Floyed(int n)
{
    int i,j,k;
    double max = 0;

    for(k = 0; k < n;k++)       
        for(i = 0;i < n;i++)
            for(j = 0;j < n;j++)
                W[i][j] = MIN(W[i][j],W[i][k]+W[k][j]);

    for(i=0;i<n;i++)
        for(j=0;j<i;j++)
            if(max<W[i][j])
                max = W[i][j];
    return max;
}

double MIN(double x,double y)
{
    return (x<y)?x:y;
}