题目链接：https://vjudge.net/problem/POJ-2253
题意：给出n个点的坐标，求点1到点2的forg distance，其定义为点1到点2的所有路径中最长边的最小值。
思路：floyd真的很强大，改一下定义，dis[i][j]表示i到j的frog distance，然后枚举中间点k，转移方程是dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]))。复杂度O(n^3).
AC代码：
e<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef pair<int,int> PII; const int maxn=205; PII p[maxn]; int n,cas; double dis[maxn][maxn]; double getdis(PII p1,PII p2){ return sqrt((p1.first-p2.first)*(p1.first-p2.first)*1.0+ (p1.second-p2.second)*(p1.second-p2.second)*1.0); } int main(){ while(scanf("%d",&n),n){ for(int i=1;i<=n;++i){ int x,y; scanf("%d%d",&x,&y); p[i]=make_pair(x,y); } for(int i=1;i<=n;++i){ dis[i][i]=0.0; for(int j=i+1;j<=n;++j) dis[i][j]=dis[j][i]=getdis(p[i],p[j]); } for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j])); printf("Scenario #%d\n",++cas); printf("Frog Distance = %.3f\n\n",dis[1][2]); } return 0; }