HDU 1245 Saving James Bond(Floyd)

HDU 1245 Saving James Bond(Floyd)

http://acm.hdu.edu.cn/showproblem.php?pid=1245

题意:你在一个圆形岛上,需要通过跳跃踩鳄鱼来逃离到正方形的岸上去.现在给你所有鳄鱼的坐标和岛的信息以及你一次能跳跃的距离,问你最少要条多少距离且最少要跳多少步?

分析:

其实本题本质上就是一道多源点多汇点的最短路径题目,不过本题需要注意的细节很多.

1.对于输入的鳄鱼坐标,如果鳄鱼当前已经在岛上,可以直接不考虑(其实就算考虑了也无所谓)

2.对于一条鳄鱼,如果计算人初始在岛上与该鳄鱼的距离?(圆形射线)

3.对于一条鳄鱼,如何计算它与岸边的最短距离?(最短距离一定是鳄鱼的x或y坐标离坐标轴的垂直距离)

4.如果人一次就能跳跃>=42.5米,那么人直接可以跳出去,只需要1次.

具体的细节还得体会代码,用Floyd算法写的,方便些.

AC代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define INF 1.0e15
using namespace std;
const int maxn = 100+10;
int n;
double D,d[maxn][maxn];
int step[maxn][maxn];
double x[maxn],y[maxn];//鳄鱼坐标
double get_dist(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
    while(scanf("%d%lf",&n,&D)==2)
    {
        int cnt=1;
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&x[cnt],&y[cnt]);
            if(fabs(x[cnt])<=7.5 && fabs(y[cnt])<=7.5) continue;
            ++cnt;
        }
        n=cnt;      //实际有效节点数:包括了超级源和超级汇点
        if(D>=42.5) //特例
        {
            printf("42.50 1\n");
            continue;
        }

        for(int i=0;i<=n;i++)//初始化
        for(int j=0;j<=n;j++)
        {
            d[i][j]= i==j?0:INF;
            step[i][j]=0;
        }

        for(int i=1;i<n;i++)//计算鳄鱼之间的距离
        for(int j=i+1;j<n;j++)
        {
            d[i][j] = d[j][i] = get_dist(x[i],y[i],x[j],y[j]);
            step[i][j] = step[j][i] = 1;
            if(d[i][j]>D)
            {
                d[i][j]=d[j][i]=INF;
                step[i][j]=step[j][i]=0;
            }
        }


        for(int i=1;i<n;i++)//添加超级源与超级汇
        {
            if(get_dist(x[i],y[i],0,0)<=D+7.5)//源点之一
            {
                d[i][0]=d[0][i]=get_dist(x[i],y[i],0,0)-7.5;
                step[i][0]=step[0][i]=1;
            }
            if(50-x[i]<=D || x[i]+50<=D || 50-y[i]<=D ||y[i]+50<=D)//汇点之一
            {
                d[i][n]=d[n][i]=min(min(50-x[i],x[i]+50),min(50-y[i],y[i]+50));
                step[i][n]=step[n][i]=1;
            }
        }

        for(int k=0;k<=n;k++)//Floyd,此处可以改为Dijkstra
        for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        if(d[i][k]<INF && d[k][j]<INF && d[i][j]> d[i][k]+d[k][j])
        {
            d[i][j]= d[i][k]+d[k][j];
            step[i][j]=step[i][k]+step[k][j];
        }

        if(d[0][n]==INF) printf("can't be saved\n");
        else printf("%.2lf %d\n",d[0][n],step[0][n]);
    }
    return 0;
}