HDU 1245 Saving James Bond

HDU 1245 Saving James Bond

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

HDU 1245 Saving James Bond此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

HDU 1245 Saving James Bond

计算几何+SPFA

我已经不想看我的提交记录了。。。。

HDU 我起码WA了2页。。。。

都是浮点数惹的祸。

const double eps=1e-4;

abs(a-b)<=eps;

这样来推断相等。

总共 n 条鳄鱼,最多有 n*(n+1)/2 条路。

抽象化处理。

把 中心的起点当作 起点0 ; 最多有 n+1 条路。

把鳄鱼和周围的边界的终点都当作 n+1 ; 最多有 n+1 条

总共就仅仅存在 n+2个点。

就是计算0 和 n+1 的最短距离。

有个小优化,就是当 跳跃距离可以直接跳到岸上的时候就直接输出 42.5 1;

G++ ,C++ 都过了。

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
const double INF= 0xfffffff;
bool vis[103];
double dis[103];
int path[103];
int n;
double m;
const double eps=1e-4;
struct lx
{
    int v;
    double len;
};
vector<lx>g[103];
struct node
{
    double x,y;
} point[101];
void build()
{
    int u,v;
    for(int i=1; i<=n; i++)
    {
        double x=point[i].x;
        double y=point[i].y;
        double len;
        u=i;
        double xx,yy;
        lx now;
        xx=min(50.00-x,50.00-y);
        yy=min(50.00+x,50.00+y);
        len=min(xx,yy);
        if(len<=m)
        {
            now.v=n+1,now.len=len;
            g[u].push_back(now);
        }
        len=sqrt(x*x+y*y);
        if(len-7.5<=m)
        {
            now.len=len-7.5;
            now.v=u;
            g[0].push_back(now);
        }
        for(int j=i+1; j<=n; j++)
        {
            len=sqrt((x-point[j].x)*(x-point[j].x)+(y-point[j].y)*(y-point[j].y));
            if(len<=m)
            {
                now.len=len;
                now.v=j;
                g[u].push_back(now);
                now.v=u;
                g[j].push_back(now);
            }
        }
    }
}
void SPFA()
{
    for(int i=0; i<103; i++)
        dis[i]=INF,vis[i]=0,path[i]=INF;
    queue<int>q;
    dis[0]=0,vis[0]=1;
    q.push(0);path[0]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int j=0; j<g[u].size(); j++)
        {
            int v=g[u][j].v;
            double len=g[u][j].len;
            if(abs(dis[v]-dis[u]-len)<=eps)
            {
                if(path[v]>path[u]+1)
                path[v]=path[u]+1;
            }
            else if(dis[v]>=dis[u]+len)
            {
                dis[v]=dis[u]+len;
                path[v]=path[u]+1;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(abs(dis[n+1]-INF)<=eps)
        puts("can't be saved");
    else
        printf("%.2f %d\n",dis[n+1],path[n+1]);
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0; i<103; i++)
            g[i].clear();
        for(int i=1; i<=n; i++)
            scanf("%lf%lf",&point[i].x,&point[i].y);
        if(m>=42.50)
        {
            puts("42.50 1");
            continue;
        }
        build();
        SPFA();
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117989.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 6个技巧,让你十年前的老电脑流畅起来。

    6个技巧,让你十年前的老电脑流畅起来。电脑越来的越久,运行速度就会越慢,如何让老旧的电脑重新快起来呢?以下6个技巧,请收好了。1、换Win10系统俗话说,重装系统能解决90%的问题。此话不假,对于一些卡的不行的电脑这一招是最有效的。Windows10系统,1GHz的CPU、1GB内存、16GB硬盘就能流畅的运行,即便是十年前的电脑也能流畅运行。还在抱着XP系统的用户,不妨试一试,XP已然不是最好的系统了,虽然十年前…

  • myeclipse6.5注册码在线生成_机器码生成注册码在线

    myeclipse6.5注册码在线生成_机器码生成注册码在线在线生成网址http://key.858game.com/index.jspmyeclipse8.5注册码列表:      lipengxin      yLR8ZC-855575-645657520873808      2016-01-0310:18:40                       myeclipse10.注册

  • pycharm2021.12.12永久激活【2021免费激活】

    (pycharm2021.12.12永久激活)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html23…

  • Java ListNode 链表

    JavaListNode链表基本结构基本初始化添加构造方法初始化范型写法创建与遍历链表插入节点替换节点删除节点补充说明基本结构链表是一种数据结构,由数据和指针构成,JavaListNode链表是一种由Java自定义实现的链表结构。基本初始化classListNode{//类名:Java类就是一种自定义的数据结构intval;//数据:节点数据ListNodenext;//对象:引用下一个节点对象。在Jav

  • Java 时间字符串转换为date[通俗易懂]

    Java 时间字符串转换为date[通俗易懂]Java时间字符串转换为date

  • ERROR running qmake

    ERROR running qmake1>ReadingQtconfiguration(D:/SoftWare/QT5.9.3/5.9.3/msvc2017_64/bin/qmake)1>GHViewerDetect.vcxproj:error:ERRORrunningqmake1>GHViewerDetect.vcxproj:error:qmake:(D:/SoftWare/QT5.9.3/5.9.3/msvc2017_64/bin/qmake)1>GHViewerDetect.vcx

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号