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

AG-UI协议实战:构建智能体驱动的动态前端交互系统

1. AG-UI协议&#xff1a;智能体与前端交互的新范式 第一次听说AG-UI协议时&#xff0c;我正在为一个电商项目头疼——后台AI生成的商品推荐总需要手动同步到前端&#xff0c;代码里到处是setState和事件监听。直到发现这个协议&#xff0c;才明白原来智能体和前端可以像两个老…...

3步实现GitHub资源精准提取:开发者必备的效率工具

3步实现GitHub资源精准提取&#xff1a;开发者必备的效率工具 【免费下载链接】DownGit github 资源打包下载工具 项目地址: https://gitcode.com/gh_mirrors/dow/DownGit 你是否曾遇到这样的困境&#xff1a;急需从GitHub仓库中获取一个特定文件夹&#xff0c;却不得不…...

别再只查‘待办’了!Flowable任务查询的三种高级场景:拾取、归还与候选组权限控制详解

Flowable任务管理的三大高阶场景&#xff1a;从候选池到个人待办的完整控制策略 当我们在处理业务流程自动化时&#xff0c;任务管理往往是最容易被简化的环节。大多数开发者止步于基础的待办列表查询&#xff0c;却忽视了任务流转过程中的精细控制。本文将带您深入Flowable任务…...

从零到专业:League Director 让你的英雄联盟回放变成电影级大片

从零到专业&#xff1a;League Director 让你的英雄联盟回放变成电影级大片 【免费下载链接】leaguedirector League Director is a tool for staging and recording videos from League of Legends replays 项目地址: https://gitcode.com/gh_mirrors/le/leaguedirector …...

3层防护构建个人AI助手: Maid跨平台应用的隐私与体验革新

3层防护构建个人AI助手&#xff1a; Maid跨平台应用的隐私与体验革新 【免费下载链接】maid Maid is a free and open source application for interfacing with llama.cpp models locally, and with Anthropic, DeepSeek, Ollama, Mistral and OpenAI models remotely. 项目…...

OpenShamrock:零基础搭建QQ智能交互系统完全指南

OpenShamrock&#xff1a;零基础搭建QQ智能交互系统完全指南 【免费下载链接】OpenShamrock A Bot Framework based on Xposed with OneBot11 项目地址: https://gitcode.com/gh_mirrors/op/OpenShamrock 核心价值解析&#xff1a;为什么选择OpenShamrock构建QQ机器人&a…...

从理论到实践:基于状态观测器的闭环系统设计与MATLAB仿真

1. 当状态看不见时&#xff0c;我们如何控制一个系统&#xff1f; 想象一下你在驾驶一辆汽车&#xff0c;但仪表盘全部失灵——看不到车速、转速、油量&#xff0c;甚至连方向盘转角都不知道。这时候如果要保持车道&#xff0c;你会怎么做&#xff1f;这就是控制工程中经典的状…...

新能源车BMS低压管理避坑指南:如何解决上下电时序中的典型问题

新能源车BMS低压管理避坑指南&#xff1a;如何解决上下电时序中的典型问题 在新能源汽车的电池管理系统&#xff08;BMS&#xff09;开发中&#xff0c;低压上下电时序控制是确保系统稳定运行的关键环节。许多开发团队在实际项目中都会遇到信号冲突、时序错乱、异常处理机制不完…...

香橙派Armbian系统下,用apt一键安装OpenCV的完整流程(含GPG报错解决)

香橙派Armbian系统下OpenCV-Python极简安装指南&#xff1a;绕过源码编译的终极方案 在单板计算机领域&#xff0c;香橙派凭借其出色的性价比逐渐崭露头角。当开发者尝试在这类ARM架构设备上构建计算机视觉应用时&#xff0c;OpenCV往往是不可或缺的核心工具。然而&#xff0c;…...

QT 5.14.0实战:手把手教你用QLineEdit打造一个带验证码的登录框(附完整样式代码)

QT 5.14.0实战&#xff1a;手把手教你用QLineEdit打造一个带验证码的登录框&#xff08;附完整样式代码&#xff09; 在GUI开发中&#xff0c;登录界面是最基础也最考验细节的组件之一。一个优秀的登录框不仅需要功能完整&#xff0c;还要在用户体验上下足功夫——比如实时输入…...