Frogger--poj2253

http://poj.org/problem?id=2253
标题:The frog distance(humans also call it minimax distance)between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.この言葉は重要で、カエルが一度に少なくともどれだけ遠くまで跳んで相手のところに着くかを求める.すなわち、全ての経路における各経路における最大距離の最小値を求める(経路上の最大エッジ重みを最小にする1~2の経路を求める)
floydでの更新距離を更新最小の最大エッジ権に変更します.

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define INF 0xfffffff

#define N 1100

using namespace std;

int n;

double maps[N][N];



struct node

{

    int x,y;

}a[N];

void Floyd()

{

    int i,j,k;

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

    {

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

        {

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

            {

                maps[i][j]=min(maps[i][j],max(maps[i][k],maps[k][j]));

            }

        }

    }

}



int main()

{

    int i,j,k,x,y,t=1;



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

    {

        memset(a,0,sizeof(a));



        k=1;



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

        {

            scanf("%d%d",&x,&y);



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

            {

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



                maps[i][j]=maps[j][i]=d;

            }



            a[k].x=x,a[k].y=y,k++;

        }

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



            maps[i][i]=0;



        Floyd();



        printf("Scenario #%d
Frog Distance = %.3f

",t++,maps[1][2]);

    }

    return 0;

}

View Code
 

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define INF 0xfffffff

#define N 1100

using namespace std;

int n,vis[N];

double maps[N][N],dist[N],ans;

struct node

{

    int x,y;

}a[N];

void Dij()

{

    int i,j,index;

    dist[1]=0;

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

    {

        double Min=INF;

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

        {

            if(vis[j]==0&&Min>=dist[j])

                Min=dist[j],index=j;

        }

        vis[index]=1;

        if(ans<dist[index]&&dist[index]!=INF)

            ans=dist[index];

        if(index==2)

            return ;

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

        {

            if(vis[j]==0)

                dist[j]=min(dist[j],maps[index][j]);

        }

    }

}

int main()

{

    int i,j,k,x,y,t=1;

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

    {

        memset(vis,0, sizeof(vis));

        memset(a,0,sizeof(a));

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

            dist[i]=INF;

        k=1;

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

        {

            scanf("%d%d",&x,&y);

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

            {

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

                maps[i][j]=maps[j][i]=d;

            }

            a[k].x=x,a[k].y=y,k++;

        }

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

            maps[i][i]=0;

        ans=0;

        Dij();

        printf("Scenario #%d
Frog Distance = %.3f

",t++,ans);

    }

    return 0;

}

View Code