floyd的变种
#include <stdio.h>
#include <math.h>
int n, times= 1;
int data[300][3];
int num[300][300];
int dist(int x1, int y1, int x2, int y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
int max(int a, int b)
{
return a>b?a:b;
}
void floyd()
{
for ( int k = 0 ; k < n ; k++ )
for ( int i = 0 ; i < n ; i++ )
for ( int j = 0 ; j < n ; j++ )
if ( num[i][k] < num[i][j] && num[k][j] < num[i][j] )
num[i][j]= max(num[i][k], num[k][j]);
}
int main()
{
while ( scanf("%d", &n), n )
{
int i, j;
for ( i = 0 ; i < n ; i++ )
scanf("%d%d", data[i], data[i]+1);
for ( i = 0 ; i < n ; i++ )
for ( j = 0 ; j < n ; j++ )
num[i][j]= num[j][i]= dist(data[i][0], data[i][1], data[j][0], data[j][1]);
floyd();
printf("Scenario #%d\nFrog Distance = %.3f\n\n", times++, sqrt(num[0][1]));
}
return 0;
}