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

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 个点的无向图&#xff0c;其中 edges[i] [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。 同时给你一个数组 disappear &#xff0c;其中 disappear[i] 表示节点 i 从图中消失的时间点&#xff0…...

FastAPI 学习之路(五十二)WebSockets(八)接受/发送json格式消息

前面我们发送的大多数都是text类型的消息&#xff0c;对于text消息来说&#xff0c;后端处理出来要麻烦的多&#xff0c;那么我们可以不可以传递json格式的数据&#xff0c;对于前后端来说都比较友好&#xff0c;答案是肯定的&#xff0c;我们需要做下处理。 首先&#xff0c;…...

Go语言并发编程-案例_3

案例 并发目录大小统计 业务逻辑 统计目录的文件数量和大小&#xff08;或其他信息&#xff09;。示例输出&#xff1a; // 某个目录&#xff1a;2637 files 1149.87 MB 实现思路 给定一个或多个目录&#xff0c;并发的统计每个目录的size&#xff0c;最后累加到一起。 当…...

pikachu之跨站脚本攻击(x‘s‘s)

1get型 输入a看一下 接着输入<a> 发现<>没有被过滤当做标签处理了 尝试在表单提交的框里面&#xff0c;输入xss语句 尝试输入<script>alert(1)</script> 发现有长度限制 因为这里是get请求 get请求的特点是&#xff1a;传参是在url中的 所以我们可以在…...

Qt模型/视图架构——委托(delegate)

一、为什么需要委托 模型&#xff08;model&#xff09;用来数据存储&#xff0c;视图&#xff08;view&#xff09;用来展示数据。因此&#xff0c;模型/视图架构是一种将数据存储和界面展示分离的编程方法。具体如下图所示&#xff1a; 由图可知&#xff0c;模型向视图提供数…...

python3.11SSL: SSLV3_ALERT_HANDSHAKE_FAILURE

参考&#xff1a;python request包 版本不兼容 报错sslv3 alert handshake failure 解决方法-CSDN博客 修改&#xff1a;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构建的目标检测系统&#xff0c;不仅极大地增强了实时目标识别的能力&#xff0c;还通过其直观的用户界面实现了对图片、视频乃至摄像头输入的无缝支持。该系统利用YOLOv10的高效检测算法&#xff0c;能够快速准确地识别图像中的多个对象&#xff0c;并标注…...

开源模型应用落地-FastAPI-助力模型交互-进阶篇(三)

一、前言 FastAPI 的高级用法可以为开发人员带来许多好处。它能帮助实现更复杂的路由逻辑和参数处理&#xff0c;使应用程序能够处理各种不同的请求场景&#xff0c;提高应用程序的灵活性和可扩展性。 在数据验证和转换方面&#xff0c;高级用法提供了更精细和准确的控制&#…...

机器人及其相关工科专业课程体系

机器人及其相关工科专业课程体系 前言传统工科专业机械工程自动化/控制工程计算机科学与技术 新兴工科专业智能制造人工智能机器人工程 总结Reference: 前言 机器人工程专业是一个多领域交叉的前沿学科&#xff0c;涉及自然科学、工程技术、社会科学、人文科学等相关学科的理论…...

C#数字医学影像系统(RIS/PACS)源码,Oracle数据库,C/S架构,运行稳定

数字医学影像系统&#xff08;RIS/PACS&#xff09;源码&#xff0c;三甲以下的医院都能满足。PACS 系统全套成品源码。 开发技术&#xff1a;C/S架构&#xff0c;C#开发语言&#xff0c;数据库服务器采用Oracle数据库。 医学影像存储与传输系统&#xff0c;融合了医学信息化…...

Spring-Boot基础--yaml

目录 Spring-Boot配置文件 注意&#xff1a; YAML简介 YAML基础语法 YAML:数据格式 YAML文件读取配置内容 逐个注入 批量注入 ConfigurationProperties 和value的区别 Spring-Boot配置文件 Spring-Boot中不用编写.xml文件&#xff0c;但是spring-Boot中还是存在.prope…...

C/C++蓝屏整人代码

文章目录 &#x1f4d2;程序效果 &#x1f4d2;具体步骤 1.隐藏任务栏 2.调整cmd窗口大小 3.调整cmd窗口屏幕颜色 4.完整代码 &#x1f4d2;代码详解 &#x1f680;欢迎互三&#x1f449;&#xff1a;程序猿方梓燚 &#x1f48e;&#x1f48e; &#x1f680;关注博主&a…...

【Android安全】Ubuntu 下载、编译 、刷入Android-8.1.0_r1

0. 环境准备 Ubuntu 16.04 LTS&#xff08;预留至少95GB磁盘空间&#xff0c;实测占94.2GB&#xff09; Pixel 2 XL 要买欧版的&#xff0c;不要美版的。 欧版能解锁BootLoader、能刷机。 美版IMEI里一般带“v”或者"version"&#xff0c;这样不能解锁BootLoader、…...

HBuilder X3.4版本中使用uni-app自定义组件

HBuilder X3.4版本中使用uni-app自定义组件 这是我的小程序页面结构 方式一&#xff1a;导入components 1.创建componets文件&#xff0c;并编写你的组件页面 <template><view class"my-search-container"><!-- 使用 view 组件模拟 input 输入框的样…...

PHP基础语法(一)

一、初步语法 1、PHP代码标记&#xff1a;以 <?php 开始&#xff0c;以 ?> 结束&#xff1b; 2、PHP注释&#xff1a;行注释&#xff1a;//&#xff08;双斜杠&#xff09;或# 块注释&#xff1a;/* */ 3、PHP语句分隔符&#xff1a; 1&#xff09;在PHP中&#…...

Python项目打包与依赖管理指南

在Python开发中&#xff0c;python文件需要在安装有python解释器的计算机的电脑上才能运行&#xff0c;但是在工作时&#xff0c;我们需要给客户介绍演示项目功能时并不一定可以条件安装解释器&#xff0c;而且这样做非常不方便。这时候我们可以打包项目&#xff0c;用于给客户…...

矿产资源潜力预测不确定性评价

研究目的&#xff1a; 不确定性评估&#xff1a; 到底什么叫不确定性&#xff0c;简单来说就是某区域内的矿产资源量&#xff0c;并不确定到底有多少&#xff0c;你需要给出一个评估或者分布。 研究方法&#xff1a; 1.以模糊集来表示某些量&#xff1a; 关于什么是模糊集&am…...

食堂采购系统开发:从需求分析到上线实施的完整指南

本篇文章&#xff0c;笔者将详细介绍食堂采购系统从需求分析到上线实施的完整过程&#xff0c;旨在为开发团队和管理者提供一个系统化的指南。 一、需求分析 1.用户需求 常见的需求包括&#xff1a; -采购计划管理 -供应商管理 -库存管理 -成本控制 -报表生成 2.系统功…...

C++ 数据结构

C 数据结构 引言 数据结构是计算机科学中的一个核心概念&#xff0c;它涉及到如何在计算机中组织和存储数据&#xff0c;以便高效地进行数据访问和修改。C作为一种高效的编程语言&#xff0c;提供了丰富的内置数据类型和库&#xff0c;支持各种复杂的数据结构实现。本文将探讨…...

Elasticsearch:评估搜索相关性 - 第 1 部分

作者&#xff1a;来自 Elastic Thanos Papaoikonomou, Thomas Veasey 这是一系列博客文章中的第一篇&#xff0c;讨论如何在更好地理解 BEIR 基准的背景下考虑评估你自己的搜索系统。我们将介绍具体的技巧和技术&#xff0c;以便在更好地理解 BEIR 的背景下改进你的搜索评估流程…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space

问题&#xff1a;IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案&#xff1a;将编译的堆内存增加一点 位置&#xff1a;设置setting-》构建菜单build-》编译器Complier...

aurora与pcie的数据高速传输

设备&#xff1a;zynq7100&#xff1b; 开发环境&#xff1a;window&#xff1b; vivado版本&#xff1a;2021.1&#xff1b; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程&#xff0c;pc通过pcie传输给fpga&#xff0c;fpga再通过aur…...