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

题意：给出两只青蛙的坐标A、B，和其他的n-2个坐标，任一两个坐标点间都是双向连通的。显然从A到B存在至少一条的通路，每一条通路的元素都是这条通路中前后两个点的距离，这些距离中又有一个最大距离。现在要求求出所有通路的最大距离，并把这些最大距离作比较，把最小的一个最大距离作为青蛙的最小跳远距离。

有一个明显的方法就是dfs一遍但是肯定会te，所以可以考虑一下用dp的思想。

类似记忆化搜索的思想，由于数据比较小所以不用记忆化搜索也行直接利用套3层for

dp[i][j]表示从i点到j点的minimax distance（就是题目所要求的）mmp[i][j]表示i

点到j点的距离。

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

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

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

                    MIN = max(mmp[i][k] , mmp[k][j]);

                    MIN2 = max(dp[i][k] , dp[k][j]);

                    dp[i][j] = min(dp[i][j] , min(MIN , MIN2));

                    dp[j][i] = dp[i][j];

                }

            }

        }

其实这3层for也是利用了floyd的思想。

#include <iostream>#include <cstring>#include <string>#include <cmath>#include <cstdio>using namespace std;double mmp[210][210] , dp[210][210] , MIN , MIN2;int n , x , y;struct TnT {    int x , y , num;};bool vis[220];int main() {    int ans = 0;    while(scanf("%d" , &n)) {        ans++;        if(!n)            break;        TnT T[210];        for(int i = 1 ; i <= n ; i++) {            scanf("%d%d" , &x , &y);            T[i].num = i;            T[i].x = x;            T[i].y = y;        }        for(int i = 1 ; i <= n ; i++) {            for(int j = 1 ; j <= n ; j++) {                mmp[i][j] = (double)400000;                dp[i][j] = (double)400000;            }        }        for(int i = 1 ; i <= n; i++) {            int x1 = T[i].x , y1 = T[i].y , pos1 = T[i].num , x2 , y2 , pos2 , m;            for(int j = 1 ; j <= n ; j++) {                x2 = T[j].x , y2 = T[j].y ,  pos2 = T[j].num;                m = 1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2);                mmp[pos1][pos2] = min(mmp[pos1][pos2] , 1.0 * sqrt(double(m)));                mmp[pos2][pos1] = min(mmp[pos1][pos2] , mmp[pos2][pos1]);            }        }        for(int k = 1 ; k <= n ; k++) {            for(int i = 1 ; i <= n ; i++) {                for(int j = 1 ; j <= n ; j++) {                    MIN = max(mmp[i][k] , mmp[k][j]);                    MIN2 = max(dp[i][k] , dp[k][j]);                    dp[i][j] = min(dp[i][j] , min(MIN , MIN2));                    dp[j][i] = dp[i][j];                }            }        }        printf("Scenario #%d\n" , ans);        printf("Frog Distance = %.3f\n\n" , dp[1][2]);    }    return 0;}

poj 2253 Frogger（floyd变形）