3112. 访问消失节点的最少时间 Medium
给你一个二维数组 edges 表示一个 n 个点的无向图,其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。
同时给你一个数组 disappear ,其中 disappear[i] 表示节点 i 从图中消失的时间点,在那一刻及以后,你无法再访问这个节点。
注意,图有可能一开始是不连通的,两个节点之间也可能有多条边。
请你返回数组 answer ,answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ,那么 answer[i] 为 -1 。
示例 1:

输入:n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]
输出:[0,-1,4]
解释:
我们从节点 0 出发,目的是用最少的时间在其他节点消失之前到达它们。
·对于节点 0 ,我们不需要任何时间,因为它就是我们的起点。
·对于节点 1 ,我们需要至少 2 单位时间,通过 edges[0] 到达。但当我们到达的时候,它已经消失了,所以我们无法到达它。
·对于节点 2 ,我们需要至少 4 单位时间,通过 edges[2] 到达。
示例 2:

输入:n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]
输出:[0,2,3]
解释:
我们从节点 0 出发,目的是用最少的时间在其他节点消失之前到达它们。
·对于节点 0 ,我们不需要任何时间,因为它就是我们的起点。
·对于节点 1 ,我们需要至少 2 单位时间,通过 edges[0] 到达。
·对于节点 2 ,我们需要至少 3 单位时间,通过 edges[0] 和 edges[1] 到达。
示例 3:
输入:n = 2, edges = [[0,1,1]], disappear = [1,1]
输出:[0,-1]
解释:
当我们到达节点 1 的时候,它恰好消失,所以我们无法到达节点 1 。
提示:
·1 <= n <= 5 * 104
·0 <= edges.length <= 105
·edges[i] == [ui, vi, lengthi]
·0 <= ui, vi <= n - 1
·1 <= lengthi <= 105
·disappear.length == n
·1 <= disappear[i] <= 105
题目大意:只有在各结点的规定时间内才能访问各结点的情况下计算从0到达各结点的最短时间。
分析:
(1)由题可知这是单源最短路径问题,因此使用dijkstra算法;
(2)由于题中结点个数较多,因此使用优先级队列存储已访问过的结点中可以直接到达的未访问过的结点来加速查找距离0结点最近且未访问过的点;
(3)对于在规定时间外访问的结点只需不将其加入优先级队列即可。
class Solution {
public:vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {int x,y,t,node,time,nt;vector<int> ans(n,-1);priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;vector<vector<pair<int,int>>> map(n);for(const auto& edge:edges){x=edge[0];y=edge[1];t=edge[2];if(x==y) continue;map[x].emplace_back(y,t);map[y].emplace_back(x,t);}q.emplace(0,0);ans[0]=0;while(q.size()){auto [time,node]=q.top();q.pop();if(time!=ans[node]) continue;for(const auto& [nextNode,nextTime]:map[node]){if((nt=time+nextTime)<disappear[nextNode]&&(ans[nextNode]==-1)||nt<ans[nextNode]){ans[nextNode]=nt;q.emplace(nt,nextNode);}}}return ans;}
};相关文章:
3112. 访问消失节点的最少时间 Medium
给你一个二维数组 edges 表示一个 n 个点的无向图,其中 edges[i] [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。 同时给你一个数组 disappear ,其中 disappear[i] 表示节点 i 从图中消失的时间点࿰…...
FastAPI 学习之路(五十二)WebSockets(八)接受/发送json格式消息
前面我们发送的大多数都是text类型的消息,对于text消息来说,后端处理出来要麻烦的多,那么我们可以不可以传递json格式的数据,对于前后端来说都比较友好,答案是肯定的,我们需要做下处理。 首先,…...
Go语言并发编程-案例_3
案例 并发目录大小统计 业务逻辑 统计目录的文件数量和大小(或其他信息)。示例输出: // 某个目录:2637 files 1149.87 MB 实现思路 给定一个或多个目录,并发的统计每个目录的size,最后累加到一起。 当…...
pikachu之跨站脚本攻击(x‘s‘s)
1get型 输入a看一下 接着输入<a> 发现<>没有被过滤当做标签处理了 尝试在表单提交的框里面,输入xss语句 尝试输入<script>alert(1)</script> 发现有长度限制 因为这里是get请求 get请求的特点是:传参是在url中的 所以我们可以在…...
Qt模型/视图架构——委托(delegate)
一、为什么需要委托 模型(model)用来数据存储,视图(view)用来展示数据。因此,模型/视图架构是一种将数据存储和界面展示分离的编程方法。具体如下图所示: 由图可知,模型向视图提供数…...
python3.11SSL: SSLV3_ALERT_HANDSHAKE_FAILURE
参考:python request包 版本不兼容 报错sslv3 alert handshake failure 解决方法-CSDN博客 修改:Python311\Lib\site-packages\urllib3\util\ssl_.py 新版本3.11里默认没有DEFAULT_CIPHERS 补回来: #__imported from 3.6.8 # A secure default. # So…...
[深度学习]基于yolov10+streamlit目标检测演示系统设计
YOLOv10结合Streamlit构建的目标检测系统,不仅极大地增强了实时目标识别的能力,还通过其直观的用户界面实现了对图片、视频乃至摄像头输入的无缝支持。该系统利用YOLOv10的高效检测算法,能够快速准确地识别图像中的多个对象,并标注…...
开源模型应用落地-FastAPI-助力模型交互-进阶篇(三)
一、前言 FastAPI 的高级用法可以为开发人员带来许多好处。它能帮助实现更复杂的路由逻辑和参数处理,使应用程序能够处理各种不同的请求场景,提高应用程序的灵活性和可扩展性。 在数据验证和转换方面,高级用法提供了更精细和准确的控制&#…...
机器人及其相关工科专业课程体系
机器人及其相关工科专业课程体系 前言传统工科专业机械工程自动化/控制工程计算机科学与技术 新兴工科专业智能制造人工智能机器人工程 总结Reference: 前言 机器人工程专业是一个多领域交叉的前沿学科,涉及自然科学、工程技术、社会科学、人文科学等相关学科的理论…...
C#数字医学影像系统(RIS/PACS)源码,Oracle数据库,C/S架构,运行稳定
数字医学影像系统(RIS/PACS)源码,三甲以下的医院都能满足。PACS 系统全套成品源码。 开发技术:C/S架构,C#开发语言,数据库服务器采用Oracle数据库。 医学影像存储与传输系统,融合了医学信息化…...
Spring-Boot基础--yaml
目录 Spring-Boot配置文件 注意: YAML简介 YAML基础语法 YAML:数据格式 YAML文件读取配置内容 逐个注入 批量注入 ConfigurationProperties 和value的区别 Spring-Boot配置文件 Spring-Boot中不用编写.xml文件,但是spring-Boot中还是存在.prope…...
C/C++蓝屏整人代码
文章目录 📒程序效果 📒具体步骤 1.隐藏任务栏 2.调整cmd窗口大小 3.调整cmd窗口屏幕颜色 4.完整代码 📒代码详解 🚀欢迎互三👉:程序猿方梓燚 💎💎 🚀关注博主&a…...
【Android安全】Ubuntu 下载、编译 、刷入Android-8.1.0_r1
0. 环境准备 Ubuntu 16.04 LTS(预留至少95GB磁盘空间,实测占94.2GB) Pixel 2 XL 要买欧版的,不要美版的。 欧版能解锁BootLoader、能刷机。 美版IMEI里一般带“v”或者"version",这样不能解锁BootLoader、…...
HBuilder X3.4版本中使用uni-app自定义组件
HBuilder X3.4版本中使用uni-app自定义组件 这是我的小程序页面结构 方式一:导入components 1.创建componets文件,并编写你的组件页面 <template><view class"my-search-container"><!-- 使用 view 组件模拟 input 输入框的样…...
PHP基础语法(一)
一、初步语法 1、PHP代码标记:以 <?php 开始,以 ?> 结束; 2、PHP注释:行注释://(双斜杠)或# 块注释:/* */ 3、PHP语句分隔符: 1)在PHP中&#…...
Python项目打包与依赖管理指南
在Python开发中,python文件需要在安装有python解释器的计算机的电脑上才能运行,但是在工作时,我们需要给客户介绍演示项目功能时并不一定可以条件安装解释器,而且这样做非常不方便。这时候我们可以打包项目,用于给客户…...
矿产资源潜力预测不确定性评价
研究目的: 不确定性评估: 到底什么叫不确定性,简单来说就是某区域内的矿产资源量,并不确定到底有多少,你需要给出一个评估或者分布。 研究方法: 1.以模糊集来表示某些量: 关于什么是模糊集&am…...
食堂采购系统开发:从需求分析到上线实施的完整指南
本篇文章,笔者将详细介绍食堂采购系统从需求分析到上线实施的完整过程,旨在为开发团队和管理者提供一个系统化的指南。 一、需求分析 1.用户需求 常见的需求包括: -采购计划管理 -供应商管理 -库存管理 -成本控制 -报表生成 2.系统功…...
C++ 数据结构
C 数据结构 引言 数据结构是计算机科学中的一个核心概念,它涉及到如何在计算机中组织和存储数据,以便高效地进行数据访问和修改。C作为一种高效的编程语言,提供了丰富的内置数据类型和库,支持各种复杂的数据结构实现。本文将探讨…...
Elasticsearch:评估搜索相关性 - 第 1 部分
作者:来自 Elastic Thanos Papaoikonomou, Thomas Veasey 这是一系列博客文章中的第一篇,讨论如何在更好地理解 BEIR 基准的背景下考虑评估你自己的搜索系统。我们将介绍具体的技巧和技术,以便在更好地理解 BEIR 的背景下改进你的搜索评估流程…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
