题意简述

湖中有N（2<=N<=200）块石头，标号从1到N。青蛙1在石头1上，青蛙2在石头2上。给定所有的石头坐标。青蛙1试图从石头1到石头2来找青蛙2，它可以经由任意石头组成的路径。在所有可能路径中找出一条路径，使其中最长的一步的长度小于其他路径中最长的一步的长度。

本题可以化简为，点1与点2间存在若干条路径，每条路径中都存在最长的一条边。找出一条路径使得该路径最长边的长度小于其他任意路径最长边。

 算法分析

本题的解法之一是Dijkstra的变形。

初看似乎很难把这道题与单源最短路联系在一起。但我们可以做以下分析：

Dijkstra的贪心思想是基于这样一种前提：

设A→P1→P2→P3→B是A到B的最短路，则其中任意一部分亦是最短路。例如P1→P2→P3必然是P1到P3的最短路。证明很简单。假设P1到P3存在一条更短的路，则A到B便可通过该路获得一条更短的路，与题设“A→P1→P2→P3→B是A到B的最短路”矛盾。

由此便得到了Dijkstra的松弛方程：

枚举u。if (d[v]>d[u]+w(u,v)) then d[v]←d[u]+w(u,v)

其中d为源到点最短路长度。u为中转节点。w为u到v的最短路长度。

这是否能和本题的求解过程等同呢？

对于本题，易得两点间最长边最短的路径可能不唯一。但题目只关心点1到点2所有路径中最短的最长边的长度，并不关心具体路径。所以我们在求解过程中，可以人为定义所求路径满足以下条件：

设A→P1→P2→P3→B是我们想要求得的路径，则它满足其中任意一部分亦满足最长边最短。例如P1→P2→P3亦是所有P1到P3路径中最长边最短的。

这样一来，本题的求解，也满足了与Dijkstra相似的贪心过程。它的松弛方程为：

枚举j。if(dis[j]>max(dis[k],map[k][j])) then dis[j]=max(dis[k],map[k][j])

它的意思是，枚举所有中间点k，源到j的目标路径的最长边，要么在源到k这段，要么在k到j这段。

这样，我们便把Dijkstra算法移植到了本题的求解中。除了松弛方程不同，其他部分均与Dijkstra类似。这里不再赘述。

网上的解题报告说这题还可以用最小生成树，日后补充。

Problem Status: AC。时间16ms，内存680k

程序样例

#include
#include

double max(double a,double b)
{
    return a>b?a:b;
}

double frog(int n,int a[][2])
{
    double dis[200],map[200][200],t1,t2,vis[200]={0},min;
    int i,j,k;
    for(i=0;idis[j])&&(vis[j]==0))
            {
                min=dis[j];
                k=j;
            }
        vis[k]=1;
        for(j=0;jmax(dis[k],map[k][j])))
               dis[j]=max(dis[k],map[k][j]);
    }
    return dis[1];
}

int main()
{
    int x=1,n,i,a[200][2];
    double ans;
    scanf("%d",&n;);
    while(n!=0)
    {
        for(i=0;i