POJ - 2253 Frogger（Floyd)

POJ-2253 Frogger

题意：一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会，但由于湖水太脏，他不想游泳过去而是跳过去找Fiona。 很不幸，Fiona所在的石头距离他有点远，甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也许会将这个很长的跳跃距离化成若干个短的跳跃距离。

题解：用到floyd算法； 第二个例子：第一个点到第二个点的距离为2，第一个和第二个点的距离是根2，第二个点和第三个点的距离是根2，所以青蛙为了避免跳最大距离，就先跳到三点，然后跳到2点，一共跳了两段，两段中最小的一段是根2。

C++提交，否则就WA

#include<cstdio> 
#include<cmath> 
#include<algorithm>
using namespace std;
struct Forg
{
    int x,y;
}f[201];
int main(void) 
{
     int x[201],y[201],n,q=1,inf=9999999;double e[201][201];while(~scanf("%d",&n)&&n) {
     for(int i=1;i<=n;i++) scanf("%d%d",&f[i].x,&f[i].y);/*for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) {if(i==j) e[i][j]=0;elsee[i][j]=inf;}*/for(int i=1;i<=n;i++) //对角线不需要判断 for(int j=i+1;j<=n;j++) e[i][j]=e[j][i]=abs(f[i].x-f[j].x)*abs(f[i].x-f[j].x)+abs(f[i].y-f[j].y)*abs(f[i].y-f[j].y);for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(e[i][j]>max(e[i][k],e[k][j]))//边的松弛条件e[i][j]=max(e[i][k],e[k][j]);
// e[i][j]=min(e[i][j],max(e[i][k],e[k][j]));//许多通路中最长边中的最小边printf("Scenario #%d\n",q);printf("Frog Distance = %.3lf\n",sqrt(e[1][2]));printf("\n"); q++;} return 0; 
}