Freddy Frog暗恋Fiona Frog，在他们之间有n快石头，告诉你这n快石头的坐标，第一快为Freddy Frog的坐标，第n块为Finoa Frog的坐标，Freddy可以借助石头经过任何路径到达Fiona那里，问他最小的弹跳距离是多少

与1797一样，只不过这里求的是所有 路径里最大边 中最小的那个

因此第一步取最小的那个。后面如果有更大的边，则需要松弛，因为路径上有更大的边，因此需要更新该路径的最大边。

当然用FOLYD算法也可以 后面也有：

#include<stdio.h>

#include<string.h>

#include<math.h>

const int MAXN=300;

const int INF=0x7fffffff;

int map[MAXN][MAXN];

int dist[MAXN];

int n;

struct Point

{

    int x,y;

}pnt[MAXN];

int max(int a,int b)

{

    return a>b?a:b;

}

int min(int a,int b)

{

    return a<b?a:b;

}

int _dist(Point a,Point b)

{

    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

}

void Dijkstra()

{

   int i,j,k;

   int min;

   int p[MAXN];

   for (i=1;i<=n;i++)

   {

       p[i]=0;

       dist[i]=map[1][i];//1是源点，具体的源点不同

   }

   dist[1]=0;

   p[1]=1;

   for (i=1;i<=n-1;i++)

   {

       min=INF;

       k=0;

       for (j=1;j<=n;j++)

       {

           if(!p[j] && dist[j]<min)

           {

               min=dist[j];

               k=j;

           }

       }

       if(k==0) return ;

       p[k]=1;

       for (j=1;j<=n;j++)

       {

           if(!p[j] && map[k][j]!=INF)

           {

               if(dist[j]>max(dist[k],map[k][j]))

               dist[j]=max(dist[k],map[k][j]);

           }

       }

   }

}

int main()

{

    int cas=1,i,j;

    while(scanf("%d",&n) && n)

    {

        for (i=1;i<=n;i++)

        {

            scanf("%d%d",&pnt[i].x,&pnt[i].y);

        }

        for (i=1;i<=n;i++)

            for (j=1;j<=n;j++)

            {

                if(i==j) map[i][j]=0; 

                else map[i][j]=INF;

            }

        for (i=1;i<=n;i++)

        {

            for (j=1;j<=n;j++)

            {

                    map[i][j]=_dist(pnt[i],pnt[j]);

            }

        }

        Dijkstra();

        printf("Scenario #%d\n",cas++);

        printf("Frog Distance = %.3f\n\n",sqrt(1.0*dist[2]));//在计算距离时一直没有开方，因此这里需要开方

    }

    return 0;

}

当然用FOLYD算法也可以 后面也有：

//Memory Time 

//584K   63MS 

#include<iostream>

#include<math.h>

#include<iomanip>

using namespace std;

class coordinate

{

public:

double x,y;

}point[201];

double path[201][201];   //两点间的权值

int main(void)

{

int i,j,k;

int cases=1;

while(cases)

{

/*Read in*/

int n;   //numbers of stones;

cin>>n;

if(!n)break;

for(i=1;i<=n;i++)

cin>>point[i].x>>point[i].y;

/*Compute the weights of any two points*/

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

{

double x2=point[i].x-point[j].x;

double y2=point[i].y-point[j].y;

path[i][j]=path[j][i]=sqrt(x2*x2+y2*y2);  //双向性

}

/*Floyd Algorithm*/

for(k=1;k<=n;k++)    //k点是第3点

for(i=1;i<=n-1;i++)    //主要针对由i到j的松弛,最终任意两点间的权值都会被分别松弛为最大跳的最小（但每个两点的最小不一定相同）i到i不需要计算

for(j=i+1;j<=n;j++)

if(path[i][k]<path[i][j] && path[k][j]<path[i][j])    //当边ik,kj的权值都小于ij时，则走i->k->j路线，否则走i->j路线

if(path[i][k]<path[k][j])               //当走i->k->j路线时，选择max{ik,kj},只有选择最大跳才能保证连通

path[i][j]=path[j][i]=path[k][j];

else

path[i][j]=path[j][i]=path[i][k];

cout<<"Scenario #"<<cases++<<endl;

cout<<fixed<<setprecision(3)<<"Frog Distance = "<<path[1][2]<<endl;

//fixed用固定的小数点位数来显示浮点数（包括小数位全为0)

//setprecision(3)设置小数位数为3

cout<<endl;

}

return 0;

}