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 的背景下改进你的搜索评估流程…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
