当前位置: 首页 > news >正文

Easy Glide

题意:给出起点终点坐标,然后给出可以经过的几个点,未经过这几个点的时候以v1的速度前进,一旦经过这些点就可以在3秒内以v2的速度前进,3秒之后恢复v1,问从起点到终点所需的最短时间

思路:最短路模型没什么好说的,如果采用邻接表方式存图建边会比较麻烦,很遗憾我就是用的邻接表,注意从起点出发的点只能以v1的速度前进

ac代码:

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
#define pb push_back
#define int long long
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int N=1010;
pii _point[N];
int n;
double dist[N];
bool vis[N];
pii _start,_end;
vector<pair<int,double>> g[N];
double v1,v2;
double getdist(int sx,int sy,int tx,int ty)
{return sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty));
}
double gettime(pii a,pii b,bool isv2)//isv2代表是否加速
{double len=getdist(a.first,a.second,b.first,b.second);double time;if(isv2){time=len/v2;if(time>3)time=3+(time-3)*v2/v1;}else time=len/v1;return time;
}
void dij()
{priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> q;dist[n]=0;q.push({dist[n],n});while(q.size()){int u=q.top().second;q.pop();if(vis[u])continue;vis[u]=true;for(auto [v,w]:g[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;q.push({dist[v],v});}}}
}
void solve()
{cin>>n;for(int i=0;i<=n+1;i++)dist[i]=1e9;for(int i=0;i<n;i++)cin>>_point[i].first>>_point[i].second;//将0加速点到n-1加速点的坐标存下来cin>>_start.first>>_start.second>>_end.first>>_end.second;//起点和终点的坐标cin>>v1>>v2;//假设起点为n,终点为n+1for(int i=0;i<n;i++){for(int j=0;j<n;j++)//对于每个加速点都向其他加速点以连一条边{g[i].pb({j,gettime(_point[i],_point[j],true)});}g[i].pb({n+1,gettime(_point[i],_end,true)});//再从每个点向终点连一条边}for(int i=0;i<n;i++)//从起点处发的边都是未加速的{g[n].pb({i,gettime(_start,_point[i],false)});//从起点向每个加速点连一条边}g[n].pb({n+1,gettime(_start,_end,false)});//从起点到终点连一条边dij();printf("%.12lf\n",dist[n+1]);
}
signed main()
{Mirai;int T=1;// cin>>T;while(T--){solve();}
}

相关文章:

Easy Glide

题意&#xff1a;给出起点终点坐标&#xff0c;然后给出可以经过的几个点&#xff0c;未经过这几个点的时候以v1的速度前进&#xff0c;一旦经过这些点就可以在3秒内以v2的速度前进&#xff0c;3秒之后恢复v1&#xff0c;问从起点到终点所需的最短时间 思路&#xff1a;最短路…...

ppt怎么压缩到10m以内?分享好用的压缩方法

PPT是一种常见的演示文稿格式&#xff0c;有时候文件过大&#xff0c;我们会遇到无法发送、上传的现象&#xff0c;这时候简单的解决方法就是压缩其大小&#xff0c;那怎么才能将PPT压缩到10M以内呢&#xff1f; PPT文件大小受到影响的主要因素就是以下几点&#xff1a; 1、图…...

VBA技术资料MF35:VBA_在Excel中过滤数据

【分享成果&#xff0c;随喜正能量】好马好在腿&#xff0c;好人好在嘴。不会烧香得罪神&#xff0c;不会讲话得罪人。慢慢的你就会发现&#xff0c;一颗好心&#xff0c;永远比不上一张好嘴。。 我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#…...

Debian12中为python3配置虚拟环境及在Pycharm中使用虚拟环境

在Debian 12中&#xff0c;python默认为python 3.11。 基于应用&#xff0c;现需设置虚拟环境。 1.安装venv模块 从python3.3开始&#xff0c;配置python虚拟环境&#xff0c;可用venv模块&#xff0c;更加方便了。 执行命令&#xff1a; #apt install python3.11-venv 2.…...

android app控制ros机器人一

android开发app&#xff0c;进而通过控制ros机器人&#xff0c;记录开发过程 查阅资料&#xff1a; rosjava使用较多&#xff0c;已经开发好的app也有开源的案例 rosjava GitHub https://github.com/ros-autom/RobotCA https://github.com/ROS-Mobile/ROS-Mobile-Android…...

二十章:基于弱监督语义分割的亲和注意力图神经网络

0.摘要 弱监督语义分割因其较低的人工标注成本而受到广泛关注。本文旨在解决基于边界框标注的语义分割问题&#xff0c;即使用边界框注释作为监督来训练准确的语义分割模型。为此&#xff0c;我们提出了亲和力注意力图神经网络&#xff08;A2GNN&#xff09;。按照先前的做法&a…...

webpack5 学习之路

1.视频 01-课程介绍_哔哩哔哩_bilibili 2.配套资料 依赖环境 | 尚硅谷 Web 前端之 Webpack5 教程 3.webpack 官方文档 入口起点(entry points) | webpack 中文文档 4.vue cli 官方文档 介绍 | Vue CLI 挖矿&#xff1a;Coding Tree...

VSCode C++ 调试方法

VSCode 调试 C 主要就是 .vscode 中的 launch.json 和 tasks.json 的配置。 launch.json 可以通过 vscode 界面 ——》左侧调试功能按钮——》创建 launch.json ——》C&#xff08;GDB/LLDB&#xff09;生成。 其中 launch.json 默认配置如下&#xff0c;主要配置项说明&…...

Java设计模式-命令模式

命令模式 1.命令模式含义 命令模式&#xff0c;将一个请求封装为一个对象&#xff0c;从而使你可用不同的请求对客户进行参数化。对请求排队或记录请求日志&#xff0c;以及支持可撤销的操作。 命令模式乍一看&#xff0c;有点懵懵的。即使这个定义看完&#xff0c;也是不明…...

Linux编译宏BUILD_BUG_ON_ZERO

本系列文章主要写我在阅读Linux内核过程中&#xff0c;关注的比较难以理解但又设计巧妙的代码片段&#xff08;不关注OS的各个模块的设计思想&#xff0c;此部分我准备写在“深入理解Linux Kernel”系列文章中&#xff09;&#xff0c;一来通过内核代码复习一下C语言及汇编语言…...

从Arweave开始:4EVERLAND存储签入挑战开始

嗨&#xff0c;4evers&#xff0c; 今天&#xff0c;我们热烈欢迎您参加 Galxe 上的 4EVERLAND “Arweave 入门”活动。这是一项长期的重头活动&#xff0c;所有参与的用户都有机会获得相应的奖励。 Arweave 是一种革命性的去中心化存储协议&#xff0c;为寻求安全可靠的有价…...

数据结构—链表

链表 前言链表链表的概念及结构链表的分类 无头单向非循环链表的相关实现带头双向循环链表的相关实现顺序表和链表&#xff08;带头双向循环链表&#xff09;的区别 前言 顺序表是存在一些固有的缺陷的&#xff1a; 中间/头部的插入删除&#xff0c;时间复杂度为O(N)&#xf…...

windows 10/11 修改右键新建菜单

问题&#xff1a;修改右键新建菜单内容 解决方法&#xff1a;使用软件ShellNew Settings 1.打开软件 2.根据需要取消勾选项 3.最终效果...

6.修饰符

文章目录 6.1 在一个静态方法内调用一个非静态成员为什么是非法的?6.2 静态方法和实例方法有何不同 6.1 在一个静态方法内调用一个非静态成员为什么是非法的? 由于静态方法可以不通过对象进行调用&#xff0c;因此在静态方法里&#xff0c;不能调用其他非静态变量&#xff0…...

【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】

题目截图 题目分析 关键就是记录每次操作2时&#xff0c;nums1中的1的个数这就需要实现线段树进行区间反转以及区间求和 ac code class Solution:def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:n len(nums1)m le…...

练习时长两年半的入侵检测

计算机安全的三大中心目标是&#xff1a;保密性 (Conf idential ity) 、完整性 (Integrity) 、可用性 (Availability) 。 身份认证与识别、访问控制机制、加密技术、防火墙技术等技术共同特征就是集中在系统的自身加固和防护上&#xff0c;属于静态的安全防御技术&#xff0c;…...

【弹力设计篇】聊聊隔离设计

为什么需要隔离设计 隔离其实就是Bulkheads&#xff0c;隔板。在生活中隔板的应用主要在船舱中进行设计&#xff0c;目的是为了避免因一处漏水导致整个船都沉下去。可以将故障减少在一定的范围内&#xff0c;而不是整个船体。 从架构演变来说的话&#xff0c;大多数系统都是从…...

MFC 透明窗体

如何制作透明窗体 &#xff1f;&#xff1f;&#xff1f;&#xff1f;&#xff1f; 使用SetLayeredWindowAttributes可以方便的制作透明窗体&#xff0c;此函数在w2k以上才支持,而且如果希望直接使用的话&#xff0c;可能需要下载最新的SDK。不过此函数在w2k的user32.dll里有实…...

C++笔记之vector的resize()和clear()用法

C笔记之vector的resize()和clear()用法 code review! 文章目录 C笔记之vector的resize()和clear()用法1.resize()2.clear() 1.resize() 运行 2.clear() 运行...

Vue2基础九、路由

零、文章目录 Vue2基础九、路由 1、单页应用 &#xff08;1&#xff09;单页应用是什么 单页面应用(SPA&#xff1a;Single Page Application): 所有功能在 一个html页面 上实现具体示例: 网易云音乐 https://music.163.com/ &#xff08;2&#xff09;单页面应用VS多页面…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...