題目傳送：poj2253
題目大意：青蛙A通過跳躍小石頭的方式跳到青蛙B那里去，給出青蛙A和青蛙B以及其他小石頭的坐標(biāo)。A到B的任一路徑中包含若干中間距離，找出最大中間距離。注意該題求的是所有路徑的最大中間距離中值最小的那個。

dijkstra
一毛一樣的代碼，c++過了，g++過不了，g++對double類型數(shù)據(jù)編譯時精度不夠，遇到這種情況試試換c++編譯吧

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=255;
const int inf=1e9;
int x[maxn],y[maxn];
int n,book[maxn];
double e[maxn][maxn];
double dis[maxn];
void dij(int s){
    for(int i=1;i<=n;i++){
        int mmin=inf;
        int k=-1;
        //int k;
        for(int j=1;j<=n;j++){
            if(book[j]==0&&dis[j]<mmin){
                mmin=dis[j];
                k=j;
            }
        }
        if(k==-1)break;
        book[k]=1;
        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],max(dis[k],e[k][j]));//dis[j]為從一號石頭到第j號石頭所有通路中最長邊中的最小邊
        }
    }
}
int main(){
    int cnt=0;
    while(~scanf("%d",&n)){
        if(n==0)break;
        memset(e,0,sizeof(e));//memset二維數(shù)組初始化
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x[i],&y[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                e[i][j]=e[j][i]=sqrt(double((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
            }
        }
        for(int i=1;i<=n;i++)
            dis[i]=inf;
        dis[1]=0;
        memset(book,0,sizeof(book));
        //book[1]=1;沒有對源點1的出邊松弛，所以不標(biāo)記
        dij(1);
        printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++cnt,dis[2]);
    }
    return 0;
}

最小生成樹：
學(xué)習(xí)到一個很巧妙的方法，算出所有點之間的距離，將距離從小到大排序，逐一選邊，將邊的兩點加入到一個集合里，并判斷兩只是否相遇，若相遇，此時距離就是答案

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=255;
int pre[maxn];
int px[maxn],py[maxn];
struct point{
    int x,y;
    double dis;
}s[maxn*maxn];//不能開太小，s[maxn]出錯
int Find(int x){ //判斷是否在一個集合里
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}
void merg(int x,int y){ //并查集思想
    int m=Find(x);
    int n=Find(y);
    if(m!=n)
        pre[n]=m;
}
bool cmp(point a,point b){
    return a.dis<b.dis;
}
int main(){
    int cas=0;
    int n;
    while(~scanf("%d",&n)){
        if(n==0)break;
        for(int i=1;i<=maxn;i++)
            pre[i]=i;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&px[i],&py[i]);
        }
        int cnt=1;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                s[cnt].x=i;
                s[cnt].y=j;
                //s[cnt].dis=sqrt(double(pow(px[i]-px[j],2)+pow(py[i]-py[j],2)));//編譯沒過
                s[cnt].dis=sqrt(double((px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j])));
                cnt++;
            }
        }
        sort(s,s+cnt,cmp);
        double ans;
        for(int i=1;i<=cnt;i++){
            ans=s[i].dis;
            merg(s[i].x,s[i].y);
            if(Find(pre[1])==Find(pre[2]))
                break;
        }
        printf("Scenario #%d\n",++cas);
        printf("Frog Distance = %.3lf\n\n",ans);
    }
}