当前位置: 首页 > 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 的背景下改进你的搜索评估流程…...

AR.js测试自动化终极指南:使用WebDriverIO进行高效AR应用功能测试

AR.js测试自动化终极指南&#xff1a;使用WebDriverIO进行高效AR应用功能测试 【免费下载链接】AR.js Image tracking, Location Based AR, Marker tracking. All on the Web. 项目地址: https://gitcode.com/gh_mirrors/arj/AR.js AR.js是一个强大的Web增强现实库&…...

Phi-4-Reasoning-Vision镜像免配置:Streamlit界面+预置参数一键启动

Phi-4-Reasoning-Vision镜像免配置&#xff1a;Streamlit界面预置参数一键启动 1. 项目概述 Phi-4-Reasoning-Vision是一款基于微软Phi-4-reasoning-vision-15B多模态大模型开发的高性能推理工具&#xff0c;专为双卡RTX 4090环境优化设计。这个工具最大的特点是开箱即用&…...

电镀生产线组态王6.55和三菱PLC联机仿真程序10(OPC通讯)带运行效果操作讲解视频和设计...

电镀生产线组态王6.55和三菱PLC联机仿真程序10&#xff08;OPC通讯&#xff09;带运行效果操作讲解视频和设计要求io表接线图主电路CAD曲线报表报警界面作为一名高级程序员兼IT知识写手&#xff0c;我将按照您的要求创作一篇关于电镀生产线组态王6.55和三菱PLC联机仿真程序10&a…...

颠覆叙事设计:用Arrow打造3类互动故事的零代码解决方案

颠覆叙事设计&#xff1a;用Arrow打造3类互动故事的零代码解决方案 【免费下载链接】Arrow Game Narrative Design Tool 项目地址: https://gitcode.com/gh_mirrors/arrow/Arrow 在游戏开发的黄金时代&#xff0c;叙事设计师们正面临着前所未有的创作困境&#xff1a;当…...

Android 集成第三方地图App的轻量级解决方案(高德、百度及网页版)

1. 为什么需要轻量级地图集成方案 在开发Android应用时&#xff0c;经常会遇到需要展示位置信息的需求。比如外卖App要显示商家位置&#xff0c;社交App要分享聚会地点&#xff0c;或者旅游App要标记景点位置。传统做法是直接集成高德或百度的地图SDK&#xff0c;但这会带来几个…...

Blender 3D创作套件:5大核心技术解析与完全指南

Blender 3D创作套件&#xff1a;5大核心技术解析与完全指南 【免费下载链接】blender Official mirror of Blender 项目地址: https://gitcode.com/gh_mirrors/bl/blender Blender作为一款免费开源的3D创作套件&#xff0c;为艺术家、设计师和开发者提供了从建模、动画到…...

从源码到实战:手把手拆解QEMU的vl.c如何统一管理x86和ARM虚拟机的CPU初始化

从源码到实战&#xff1a;手把手拆解QEMU的vl.c如何统一管理x86和ARM虚拟机的CPU初始化 1. 虚拟化架构设计的核心挑战 现代虚拟化平台需要支持多种硬件架构&#xff0c;而不同架构的CPU初始化流程存在显著差异。以x86和ARM为例&#xff1a; x86架构&#xff1a;需要初始化复杂的…...

RPLibs原型设计元件库:多平台UI设计效率工具指南

RPLibs原型设计元件库&#xff1a;多平台UI设计效率工具指南 【免费下载链接】rplibs Refs.cn 原型设计元件库&#xff0c;基于Axure RP 10/9&#xff0c;支持 Android、Apple、Windows、微信&#xff0c;移动、桌面平台的应用和网站原型设计。六年历程 2.8k star&#xff0c;感…...

FreeCAD参数化设计实战:3步打造你的智能机械零件库

FreeCAD参数化设计实战&#xff1a;3步打造你的智能机械零件库 【免费下载链接】FreeCAD This is the official source code of FreeCAD, a free and opensource multiplatform 3D parametric modeler. 项目地址: https://gitcode.com/GitHub_Trending/fr/freecad 你是否…...

Qt Creator工具栏字体太小看不清?一个CSS文件+启动参数轻松搞定(附Win/Mac路径)

Qt Creator工具栏字体优化指南&#xff1a;从CSS定制到跨平台适配 刚接触Qt Creator的开发者常会遇到一个看似微小却极其影响效率的问题——工具栏字体过小。这个问题在4K高分屏上尤为明显&#xff0c;开发者不得不眯着眼睛寻找功能按钮&#xff0c;严重拖慢开发节奏。本文将提…...