poj 2253 Frogger 解题报告

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

题目意思：找出从Freddy's stone  到  Fiona's stone  最短路中的最长路。 很拗口是吧，举个例子。对于 i 到 j 的一条路径，如果有一个点k， i 到 k 的距离 && k 到 j 的距离都小于 i 到 j 的距离，那么就用这两条中较大的一条来更新 i 到 j 的距离 。每两点之间都这样求出路径。最后输出 1 到 2 的距离（1：Freddy's stone   2：Fiona's stone ）。

只能说，读题能力有待改进啊~~~一开始也读不懂题意 = =

还有就是 sqrt 的参数不能是整数啦= =，要是double 或 float。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn =  + ;

 struct node

 {

     double x, y;

 }point[maxn];

 double dist[maxn][maxn];

 double distance(double x1, double x2, double y1, double y2)

 {

     double tx = x1 - x2;

     double ty = y1 - y2;

     return sqrt(tx*tx+ty*ty);

 }

 int main()

 {

     int n, l, f = , cas = ;

     while (scanf("%d", &n) != EOF && n)

     {

         if (f)

             puts("");

         f = ;

         for (l = ; l <= n; l++)

             scanf("%lf%lf", &point[l].x, &point[l].y);

         for (int i = ; i <= n; i++)

         {

             for (int j = i+; j <= n; j++)

                 dist[i][j] = dist[j][i] = distance(point[i].x, point[j].x, point[i].y, point[j].y);

         }

         // floyed

         for (int k = ; k <= n; k++)

         {

             for (int i = ; i <= n; i++)

             {

                 for (int j = ; j <= n; j++)

                 {

                     if (i != k && k != j && i != j && dist[i][j] > dist[i][k] && dist[i][j] > dist[j][k])

                     {

                         dist[i][j] = dist[j][i] =  max(dist[i][k], dist[j][k]);

                     }

                 }

             }

         }

         printf("Scenario #%d\n", ++cas);

         printf("Frog Distance = %.3lf\n", dist[][]);

     }

     return ;

 }