poj -2253 Frogger 最短路算法之dijkstra

题意：第一个点是青蛙的坐标，第二个是青蛙妹子的坐标，其他的点是石头的坐标，现在要问青蛙到青蛙妹子的地方,至少需要跳的最大距离,不是最短路问题,路可以很长,跳的石头很多,要求是跳的最大距离,最小（理解好！！！）

代码如下:(这是最短路的做法)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define db double
using namespace std;
#define INF 99999999
const int maxn=205;
db maze[maxn][maxn],low[maxn],sh;
int ca[maxn][2],vis[maxn];
int n;

void dijkstra()
{
    for(int i=0;i<n;i++){
        low[i]=maze[0][i];
        vis[i]=1;
    }
    vis[0]=0;

    int u=-1;
    for(int i=1;i<n;i++)
    {   int minn=999999;
        for(int j=0;j<n;j++)
        {
            if(vis[j] && minn>low[j]){
                minn=low[j],u=j;
            }
        }
        vis[u]=0;
        for(int j=0;j<n;j++)
        {
            low[j]=min(max(low[u],maze[u][j]),low[j]);
        }
    }
    sh=low[1];
    for(int j=0;j<n;j++){
        printf("%.2f\n",low[j]);
    }
}
int main()
{   int ans=1;
    while(~scanf("%d",&n) && n)
    {
        memset(maze,0,sizeof(maze));
        memset(ca,0,sizeof(ca));
        for(int i=0;i<n;i++)
        {
            scanf("%d %d",&ca[i][0],&ca[i][1]);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                maze[i][j]=sqrt(1.0*(ca[i][0]-ca[j][0])*(ca[i][0]-ca[j][0])+1.0*(ca[i][1]-ca[j][1])*(ca[i][1]-ca[j][1]));
            }
            maze[i][i]=0.0;
        }
        /*for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
               printf("%.3f ",maze[i][j]);
            }
            printf("\n");
        }*/
        dijkstra();
        printf("Scenario #%d\nFrog Distance = %.3f\n\n",ans++,sh);
    }
}

还可以用最小生成树做,这种方法异常巧妙.把所有的点的距离都算出来然后根据距离的长短排个序,从小到大的一次连接起来,每连一次就判断下青蛙是否和妹子相遇,如相遇则输出连的那个长度.哇，这种方法才是最好的.

代码如下:

//哇，这个方法才是真的又好敲,又好巧.!
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define db double
using namespace std;
const int maxn=205;
int pre[maxn];
db cal[maxn][2];
int cas=1;
struct point
{
    int x,y;
    db dis;
}s[maxn*maxn];

void init()
{
    for(int i=0;i<maxn;i++)
        pre[i]=i;

}

int Find(int x)
{
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}

void un(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 n;
    while(~scanf("%d",&n) && n){
        init();
        for(int i=0;i<n;i++){
            scanf("%lf %lf",&cal[i][0],&cal[i][1]);
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                s[cnt].x=i;
                s[cnt].y=j;
                s[cnt].dis=sqrt(fabs(pow(cal[i][0]-cal[j][0],2)+pow(cal[i][1]-cal[j][1],2)));
                cnt++;
            }
        }
        sort(s,s+cnt,cmp);
        db m;
        for(int i=0;i<cnt;i++){
            m=s[i].dis;
            un(s[i].x,s[i].y);
            if(Find(pre[0])==Find(pre[1]))
                break;
        }
        printf("Scenario #%d\n",cas++);
        printf("Frog Distance = %.3f\n\n",m);
    }
}