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

个人知识库构建:OpenClaw+GLM-4.7-Flash自动归档网页与文档

个人知识库构建&#xff1a;OpenClawGLM-4.7-Flash自动归档网页与文档 1. 为什么需要自动化知识管理 作为一个长期与技术文档打交道的开发者&#xff0c;我发现自己陷入了一个典型的知识管理困境&#xff1a;每天浏览的优质技术文章、收藏的GitHub仓库、订阅的RSS源越来越多&…...

Matlab图表标注全攻略:希腊字母、线型与标记符号的灵活运用

Matlab图表标注全攻略&#xff1a;希腊字母、线型与标记符号的灵活运用 科研图表是数据可视化的核心载体&#xff0c;而Matlab作为工程与科学计算领域的标杆工具&#xff0c;其绘图系统的精细控制能力往往被低估。许多研究者止步于默认图表样式&#xff0c;却不知只需掌握几个关…...

HunyuanVideo-Foley效果展示:AI生成音效在Audition中后期处理兼容性验证

HunyuanVideo-Foley效果展示&#xff1a;AI生成音效在Audition中后期处理兼容性验证 1. 音效生成技术概览 HunyuanVideo-Foley作为新一代AI音效生成模型&#xff0c;通过深度学习技术实现了从文本描述到高质量音效的端到端生成。该技术基于RTX 4090D 24GB显存和CUDA 12.4环境…...

计算机毕业设计springboot校园信息聚合搜索平台 基于SpringBoot的高校信息整合检索系统 基于爬虫技术的校园资讯一站式服务平台

计算机毕业设计springboot校园信息聚合搜索平台58y0k2mm &#xff08;配套有源码 程序 mysql数据库 论文&#xff09; 本套源码可以在文本联xi,先看具体系统功能演示视频领取&#xff0c;可分享源码参考。在数字化校园建设持续推进的背景下&#xff0c;高校内部各类信息资源呈爆…...

Intel RealSense深度相机3D点云生成终极指南:从原理到实战

Intel RealSense深度相机3D点云生成终极指南&#xff1a;从原理到实战 【免费下载链接】librealsense Intel RealSense™ SDK 项目地址: https://gitcode.com/GitHub_Trending/li/librealsense 想要快速构建高质量的三维视觉应用&#xff1f;Intel RealSense深度相机为你…...

关于前端获取DOM节点的兼容IE6的代码封装

返回所有子元素节点的代码封装// 封装一个函数&#xff0c;这个函数可以返回元素的所有子元素节点(兼容到IE6)&#xff0c;类似children的功能function getChildren(node){// 结果数组var children [];// 遍历node这个节点的所有子节点&#xff0c;判断每一个子节点的nodeType…...

企业级微信自动化框架:WeChatFerry的技术实现与商业价值分析

企业级微信自动化框架&#xff1a;WeChatFerry的技术实现与商业价值分析 【免费下载链接】WeChatFerry 微信逆向&#xff0c;微信机器人&#xff0c;可接入 ChatGPT、ChatGLM、讯飞星火、Tigerbot等大模型。Hook WeChat. 项目地址: https://gitcode.com/GitHub_Trending/we/W…...

保姆级教程:用Qt搞定蓝牙串口通信,从连接云台到指令队列完整流程

保姆级教程&#xff1a;用Qt实现蓝牙串口通信全流程实战 在智能硬件开发领域&#xff0c;蓝牙串口通信就像一座连接数字世界与物理世界的桥梁。想象一下&#xff0c;你手中的Qt程序能够通过简单的指令让云台精准转动&#xff0c;或者让智能小车按照预定路线行驶——这种"软…...

Yuxi-Know终极部署指南:5步解决大模型RAG知识库常见问题

Yuxi-Know终极部署指南&#xff1a;5步解决大模型RAG知识库常见问题 【免费下载链接】Yuxi-Know 基于大模型 RAG 知识库与知识图谱的问答平台。Llamaindex VueJS Flask Neo4j。大模型适配 OpenAI、国内主流大模型平台的模型调用、本地 vllm 部署。 项目地址: https://gitc…...

计算机专业的大学生能参加哪些比赛?看完这篇就开干吧!

计算机专业的大学生能参加哪些比赛&#xff1f;看完这篇就开干吧&#xff01; 对于计算机专业大学生而言&#xff0c;网络安全相关比赛是提升实战能力、丰富简历亮点的最佳途径。尤其是CTF竞赛和护网行动&#xff0c;已成为企业招聘时的核心参考指标。 本文梳理了适合大学生参…...