题目链接：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;
}