题目链接：Frogger

题意：两仅仅青蛙，A和B，A想到B哪里去，可是A得弹跳有限制，所以不能直接到B，可是有其它的石头作为过渡点，能够通过他们到达B，问A到B的全部路径中。它弹跳最大的跨度的最小值

PS：最小生成树过的，刚開始用Dijstra做，Kao，精度损失的厉害，对于Dijksra的变形不大会变啊，看了Discuss有人用最小生成树过，我一划拉，还真是。敲了，就过了，等会研究研究最短路的各种变形，有模板不会变，不会灵活应用，渣渣就是渣渣。

ME               Time

1017Kb          0Ms

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <string.h>

#include <algorithm>

const int INF = 1e8;

const int N = 205;

using namespace std;

struct node{

    int x,y;

}g[N];

int n,vis[N];

double mapp[N][N],dis[N];

double Prim()

{

    int pos;

    double maxe=0,minn;

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

    {

        dis[i]=mapp[1][i];

        vis[i]=0;

    }

    vis[1]=1;

    dis[1]=0;

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

    {

        minn=INF;

        pos=1;

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

           {

               if(!vis[j]&&dis[j]<minn)

            {

                pos=j;

                minn=dis[j];

            }

           }

        if(minn>maxe)

            maxe=minn;

        if(pos==2) //假设当前构树条件是2号哇，那么直接返回，无其它路线了

            return maxe;

        vis[pos]=1;

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

            if(!vis[j] &&mapp[pos][j] < dis[j])

            {

                dis[j] = mapp[pos][j];

            }

    }

    return dis[2];

}

void init(int i)

{

    double t;

    mapp[i][i]=0;

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

    {

        t=sqrt((g[i].x-g[j].x)*(g[i].x-g[j].x)+(g[i].y-g[j].y)*(g[i].y-g[j].y));

        mapp[i][j] = t;

        mapp[j][i] = t;

    }

}

int main()

{

    int c=0;

    double st;

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

    {

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

        {

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

            init(i);

        }

        st = Prim();

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

        printf("Frog Distance = %.3f\n\n",st);//看了Discuss 知道。POJ不能%.3lf

    }

    return 0;

}