534 - Frogger

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define MAX 210
using namespace std;

double arr1[MAX];
double arr2[MAX];
double mat[MAX][MAX];
long n,i,j,k,test=0;
double a,b,c;

void Floyd()
{
    for(k=0;k<n;k++)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(mat[i][j]!=0 && mat[i][k]>0 && mat[k][j]>0)
                {
                    mat[i][j]=min(mat[i][j],max(mat[i][k],mat[k][j]));
                }
            }
        }
    }
}

int main()
{
    while(scanf("%ld",&n)==1)
    {
        if(n==0)
        {
            break;
        }
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&arr1[i],&arr2[i]);
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                a=pow((arr1[i]-arr1[j]),2);
                b=pow((arr2[i]-arr2[j]),2);
                c=sqrt(a+b);
                mat[i][j]=c;
                mat[j][i]=c;
            }
        }
        Floyd();

        printf("Scenario #%ld\nFrog Distance = %.3lf\n\n",++test,mat[0][1]);
        memset(mat,0.0,sizeof(mat));
    }
    return 0;
}