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)


相关推荐

  • Maven安装配置及在idea中配置

    Maven安装配置及在idea中配置目录一、Maven是什么二、Maven安装及配置1.Maven本地安装2.Maven环境变量的配置3.Maven配置repository三、idea中创建mevenwebapp及配置1.配置settings2.创建mevenwebapp一、Maven是什么1.Maven是Apache下的一个纯java开发的开源项目,它是一个项目管理…

  • 优化算法——粒子群算法(PSO)

    优化算法——粒子群算法(PSO)一、粒子群算法的概述二、粒子群算法的流程

  • spring源码分析之事务transaction下篇

    spring源码分析之事务transaction下篇

  • 八核版9500odin3线刷通刷以及root教程

    八核版9500odin3线刷通刷以及root教程1.先准备好odin3最新版或者汉化版以及通刷包(教程最后提供下载朱雀www.zhuquewl.com)2.跟着我的步骤走,除非你RP不佳,反正我刷机成功了3.教程音量减键+HOME键+开机键出现如下画面:  4.出现如上画面按下音量加键   5.电脑上打开odin3选择你的固件,我放在桌面上(文件放哪随便了),连上手机,端口号能读出[0:COM11],读不出重新连接

  • 基于Python编程实现简单网络爬虫实现

    基于Python编程实现简单网络爬虫实现编写一个非常轻量的python代码,实现网络爬虫

  • 基于WDM的专用USB设备的驱动程序开发[通俗易懂]

    基于WDM的专用USB设备的驱动程序开发[通俗易懂]1引言目前对于诸如USB鼠标、键盘等这样的计算机标准外设,Windows系统已经提供了标准的驱动程序,用户无需再进行任何开发工作。而开发专用USB设备,需要开发专用的驱动程序。Windows2000/XP操作系统不允许用户程序直接访问硬件设备。为了实现对硬件设备的访问和控制,必须通过操作系统所认可的驱动程序对硬件设备实现间接访问和控制。驱动程序通常被认为是操作系统的组成部分,所以,开发驱动程序有严

发表回复

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

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