Q534: Frogger

// Accepted !!

// Floyd_Warshall problem

// select the minimum of longest jumps ~~ minimax

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <math.h>
#include <algorithm>
#define MAX 201

using namespace std;

double matrix[MAX][MAX];
void Floyd_Warshall(int n);

int main()
{
    int n, index = 1;
    double stone[201][2];

    while(cin >> n)
    {
        if(n == 0)
            break;

        for(int i = 1; i <= n; i++)
            cin >> stone[i][0] >> stone[i][1];

        for(int i = 1; i <= n; i++)
        {
            for(int j = i; j <= n; j++)
            {
                matrix[i][j] = sqrt(pow(stone[j][0] - stone[i][0],2) + pow(stone[j][1]-stone[i][1],2));
                matrix[j][i] = matrix[i][j];
            }
        }

        Floyd_Warshall(n);
        cout << "Scenario #" << index++ << endl;
        cout << "Frog Distance = " << setprecision(3) << setiosflags(ios::fixed) << matrix[1][2] << endl << endl;

    }

    system("PAUSE");
    return EXIT_SUCCESS;
}

void Floyd_Warshall(int n)
{
     for(int k = 1; k <= n; k++)
         for(int i = 1; i <= n; i++)
             for(int j = 1; j <= n; j++)
                 matrix[i][j] = min(matrix[i][j],max(matrix[i][k],matrix[k][j]));
}