POJ 2253 Floydアルゴリズム
1190 ワード
#include
#include
#include
#include
#define MAX 205
#define MAXN 40005
using namespace std;
struct Stone{
int x;
int y;
};
double map[MAX][MAX];
Stone rock[MAXN];
int main()
{
int cases=0;
int n,i,j,k;
while(scanf("%d",&n)&&n!=0){
memset(rock,0,sizeof(rock));
for(i=1;i<=n;i++)
scanf("%d%d",&rock[i].x ,&rock[i].y );
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{
map[i][j]=map[j][i]=sqrt((double)((rock[i].x -rock[j].x)*(rock[i].x -rock[j].x)+(rock[i].y -rock[j].y)*(rock[i].y -rock[j].y)));
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
map[i][j]=min(map[i][j],max(map[i][k],map[k][j]));
}
}
}
printf("Scenario #%d
",++cases);
printf("Frog Distance = %.3f
",map[1][2]);
}
}
110MS
Kruscal 16MS
Floyd , n3