poj 2253 Frogger(最短路 floyd)

题目:http://poj.org/problem?id=2253

题意:给出两只青蛙的坐标A、B,和其他的n-2个坐标,任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路,每一条通路的元素都是这条通路中前后两个点的距离,这些距离中又有一个最大距离。

现在要求求出所有通路的最大距离,并把这些最大距离作比较,把最小的一个最大距离作为青蛙的最小跳远距离。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std; double map[][];
int n;
void floyd()
{
int i,j,k;
for(k=; k<n; k++)
for(i=; i<n-; i++)
for(j=i+; j<n; j++)
if(map[i][k]<map[i][j] && map[k][j]<map[i][j]) //map表示从i到j 上各个通路中最大的一条当中的 最小的的
{
if(map[i][k]<map[k][j])
map[i][j]=map[j][i]=map[k][j];
else
map[i][j]=map[j][i]=map[i][k];
}
} int main()
{
int x=,i,j;
double a[],b[];
while(~scanf("%d", &n) && n)
{
memset(map,,sizeof(map));
for(i=; i<n; i++)
scanf("%lf%lf",&a[i],&b[i]); for(i = ; i < n; i++)
for(j = i+; j < n; j++)
{
map[j][i]= sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
map[i][j] = map[j][i];
} floyd();
cout<<"Scenario #"<<x++<<endl;
cout<<fixed<<setprecision()<<"Frog Distance = "<<map[][]<<endl<<endl;
}
return ;
}

……呃,这个方法还是不大能理解呀

上一篇:一个demo


下一篇:【转】setStyleSheet用法