当前位置: 首页 > 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多页面…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...