题目链接：POJ 2253
分析：找到所有通路中最小的最长边的长度。
在Dijkstra中将松弛方程由
dis[j]=min(dis[j],dis[u]+map[u][j]),
其中：dis[j]表示到达j的最短路径和，map[u][j]表示从u直接到达j的路径长度。
改为：dis[j]=min(dis[j],max(dis[u],map[u][j])),
其中dis[j]表示到达j的通路中最小的最长边的长度，map[u][j]表示从u直接到达j的路径长度。
在Floyd中将松弛方程由：
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]),
其中dis[i][j]表示从i到j的最短路径和
改为：dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
其中dis[i][j]表示从i到j的通路中最小的最长边长度。
CODE:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;const int maxint=0x3f3f3f;
const int maxnum=205;/* Dijkstra变形
double dis[maxnum],map[maxnum][maxnum];
int vis[maxnum],c[maxnum][2];
int n;double Dijkstra(int n,int c[maxnum][2])
{memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){dis[i]=maxint;for(int j=1;j<=n;j++)map[i][j]=maxint;}double t1,t2;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){t1=(c[i][0]-c[j][0])*1.0;t2=(c[i][1]-c[j][1])*1.0;map[i][j]=map[j][i]=sqrt(t1*t1+t2*t2);}}for(int i=2;i<=n;i++)dis[i]=map[1][i];vis[1]=1;dis[1]=0;for(int i=1;i<n;i++){int u=1;double tmp=maxint;for(int j=2;j<=n;j++){if((!vis[j])&&dis[j]<tmp){u=j;tmp=dis[j];}}vis[u]=1;for(int j=2;j<=n;j++){if((!vis[j])&&map[u][j]<maxint&&dis[j]>max(dis[u],map[u][j]))dis[j]=max(dis[u],map[u][j]);}}return dis[2];
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endif int cases=0;while(cin>>n&&n){for(int i=1;i<=n;i++)cin>>c[i][0]>>c[i][1];double ans=Dijkstra(n,c);printf("Scenario #%d\nFrog Distance = %.3f\n\n",++cases,ans);}return 0;
}
*/double dis[maxnum][maxnum];
int c[maxnum][2], n;double Floyd(int n,int c[maxnum][2])
{double t1,t2;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){t1=(c[i][0]-c[j][0])*1.0;t2=(c[i][1]-c[j][1])*1.0;dis[i][j]=dis[j][i]=sqrt(t1*t1+t2*t2);}} 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]));return dis[1][2];
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endif int cases=0;while(cin>>n&&n){for(int i=1;i<=n;i++)cin>>c[i][0]>>c[i][1];double ans=Floyd(n,c);printf("Scenario #%d\nFrog Distance = %.3f\n\n",++cases,ans);}return 0;
}