Frogger POJ - 2253 Floyd / dijstra

题意：

Freddy Frog暗恋Fiona Frog，在他们之间有n快石头，告诉你这n快石头的坐标，第一组为Freddy Frog的坐标，第二组为Finoa Frog的坐标，Freddy可以借助石头经过任何路径到达Fiona那里，问他最小的弹跳距离是多少（即最短路径中的最长边）。

  注意：

该题有多组测试数据，要求每组测试数据之间空一行！

Floyd 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
    double x,y;
}p[203];
double d[203][203];
int n;
void floyd()
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                if(d[i][k]<d[i][j] && d[k][j]<d[i][j])
                    d[i][j]=max(d[i][k],d[k][j]);
            }
}
int main()
{
    int k=1;
    while(~scanf("%d",&n) && n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==j)
                    d[i][j]=0;
                else
                    d[i][j]=d[j][i]=sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y) );
            }
        }
        floyd();
        printf("Scenario #%d\n",k++);
        printf("Frog Distance = %.3lf\n\n",d[0][1]);
    }

    return 0;
}
           

dijstra

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
    double x,y;
}p[203];
double d[203],map[203][203],v[203];
int n;
int main()
{
    int k=1;
    while(~scanf("%d",&n) && n)
    {
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        for(int i=0;i<n;i++)
        {
            v[i]=0;
            for(int j=0;j<n;j++)
            {
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=map[j][i]=sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y) );
            }
        }
        for(int i=0;i<n;i++)
            d[i]=map[0][i];
        v[0]=1;
        int u;
        double m;
        for(int i=0;i<n-1;i++)
        {
            m=inf;
            for(int j=0;j<n;j++)
            {
                if(!v[j] && d[j]<m)
                    m=d[u=j];
            }
            if(u==1)
                break;
            v[u]=1;
            for(int j=0;j<n;j++)
            {
                if(!v[j] && d[j]>max(d[u],map[u][j]))
                    d[j]=max(d[u],map[u][j]);
            }
        }
        printf("Scenario #%d\n",k++);
        printf("Frog Distance = %.3lf\n\n",d[1]);
    }

    return 0;
}
           

好好想想就能想明白。。。