POJ 2253 floyd求最大边的最小值

给定n个节点的坐标，求1节点到2节点的通路的边的最大值的最小值。

floyd可做，状态转移： if(G[i][j]>max(G[i][k],G[k][j]))  G[i][j]=max(G[i][k],G[k][j]);

poj上的discuss简直是百家争鸣。

可取的貌似还有二分+DFS   ， 最小生成树求最大边。

DIJ和其他最短路算法讲松弛操作改成上面的状态转移方程，应该也可以过。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double G[205][205];
int n;

inline double caldis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==k||k==j) continue;
                if(G[i][j]>max(G[i][k],G[k][j]))
                    G[i][j]=max(G[i][k],G[k][j]);
            }
        }
    }
}

int main()
{
    int cnt=0;
    while(scanf("%d",&n)&&n)
    {
        double x[205],y[205];
        scanf("%lf%lf",&x[1],&y[1]);
        for(int i=2;i<=n;i++)
        {
            scanf("%lf%lf",&x[i],&y[i]);
            for(int j=1;j<=i;j++)
            {
                G[j][i]=G[i][j]=caldis(x[i],y[i],x[j],y[j]);
            }
        }

        floyd();
        printf("Scenario #%d\n",++cnt);
        printf("Frog Distance = %.3f\n",G[1][2]);
        printf("\n");
    }
    return 0;
}