链接：poj 2253

题意：给出青蛙A,B和若干石头的坐标，现青蛙A想到青蛙B那，A可通过随意石头到达B,

问从A到B多条路径中的最长边中的最短距离

分析：这题是最短路的变形，曾经求的是路径总长的最小值，而此题是通路中最长边的最小值，每条边的权值能够通过坐标算出，由于是单源起点，直接用SPFA算法或dijkstra算法就能够了

SPFA 16MS

#include<cstdio>

#include<queue>

#include<cmath>

#include<climits>

using namespace std;

double a[205][205],dis[205];

int vis[205];

double max(double a,double b)

{

    return a>b?a:b;

}

void SPFA(int n)

{

    queue<int> q;

    int i,j;

    for(i=2;i<=n;i++){

        dis[i]=INT_MAX;

        vis[i]=0;

    }

    dis[1]=0;

    q.push(1);

    vis[1]=1;

    while(!q.empty()){

        i=q.front();

        q.pop();

        vis[i]=0;

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

            if(dis[j]>max(dis[i],a[i][j])){

                dis[j]=max(dis[i],a[i][j]);

                if(!vis[j]){

                    q.push(j);

                    vis[j]=1;

                }

            }

    }

}

int main()

{

    int i,j,n,k=0,x[205],y[205];

    while(scanf("%d",&n)!=EOF){

        if(n==0)

            break;

        k++;

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

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

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

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

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

                a[i][j]=a[j][i]=sqrt(double(x[i]-x[j])*(x[i]-x[j])+double(y[i]-y[j])*(y[i]-y[j]));

        SPFA(n);

        printf("Frog Distance = %.3lf\n\n",dis[2]);

    }

    return 0;

}