LeetCode 3112.访问消失节点的最少时间:单源最短路的Dijkstra算法

【LetMeFly】3112.访问消失节点的最少时间:单源最短路的Dijkstra算法

力扣题目链接:https://leetcode.cn/problems/minimum-time-to-visit-disappearing-nodes/

给你一个二维数组 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

解题方法:单源最短路的Dijkstra算法

关于单源最短路的Dijkstra算法的视频讲解,可以查看这个视频。

大致思路是:从起点开始,每次将所有的能一部到达的节点放入优先队列中。优先队列中存放的是每个节点的首次能到达的时间以及节点编号,能最先到达的最先出队。

每次从优先队列中取出一个元素,这样就得到了这个元素的最快到达时间。以此节点开始将所有相邻的没有确定过最短时间的节点入队。直到队列为空为止,就得到了从起点到其他任意一点的最短耗时。

关于本题,有个额外条件就是节点消失时间。很简单,在每次遍历当前节点的相邻节点时,若无法在某相邻节点消失之前到达,则不将其入队。

  • 时间复杂度 O ( n + m log ⁡ m ) O(n+m\log m) O(n+mlogm),其中 n n n是节点数量, m m m是边的数量。
  • 空间复杂度 O ( n + m ) O(n+m) O(n+m)

AC代码

C++
class Solution {
public:vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {vector<vector<pair<int, int>>> graph(n);for (vector<int>& edge : edges) {graph[edge[0]].push_back({edge[1], edge[2]});graph[edge[1]].push_back({edge[0], edge[2]});}vector<int> ans(n, -1);priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;  // [<time, toNode>, ...pq.push({0, 0});while (pq.size()) {auto [thisTime, thisNode] = pq.top();pq.pop();if (ans[thisNode] != -1) {continue;}ans[thisNode] = thisTime;for (auto [nextNode, length] : graph[thisNode]) {if (ans[nextNode] != -1 || thisTime + length >= disappear[nextNode]) {continue;}pq.push({thisTime + length, nextNode});}}return ans;}
};
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;class Solution {public int[] minimumTime(int n, int[][] edges, int[] disappear) {List<int[]>[] graph = new ArrayList[n];Arrays.setAll(graph, i -> new ArrayList<>());for (int[] edge : edges) {graph[edge[0]].add(new int[]{edge[1], edge[2]});graph[edge[1]].add(new int[]{edge[0], edge[2]});}int[] ans = new int[n];Arrays.fill(ans, -1);Queue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));pq.add(new int[]{0, 0});while (!pq.isEmpty()) {int[] temp = pq.poll();int thisTime = temp[0];int thisNode = temp[1];if (ans[thisNode] != -1) {continue;}ans[thisNode] = thisTime;for (int[] temp2 : graph[thisNode]) {int nextNode = temp2[0];int length = temp2[1];if (ans[nextNode] == -1 && thisTime + length < disappear[nextNode]) {pq.add(new int[]{thisTime + length, nextNode});}}}return ans;}
}
Python
from typing import List
import heapqclass Solution:def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:graph = [[] for _ in range(n)]for x, y, d in edges:graph[x].append((y, d))graph[y].append((x, d))ans = [-1] * npq = [(0, 0)]while pq:thisTime, thisNode = heapq.heappop(pq)if ans[thisNode] != -1:continueans[thisNode] = thisTimefor nextNode, length in graph[thisNode]:# print(nextNode, length, ans[nextNode], thisTime + length, disappear[nextNode])  #------------------# print(ans[nextNode] != -1)# print(thisTime + length < disappear[nextNode])if ans[nextNode] == -1 and thisTime + length < disappear[nextNode]:heapq.heappush(pq, (thisTime + length, nextNode))return ansif __name__ == '__main__':sol = Solution()print(sol.minimumTime(3, [[0, 1, 2], [1, 2, 1], [0, 2, 4]], [1, 1, 5]))

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/140530368

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3249772.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

大数据之数据抽取架构演变过程

架构演变之Flink架构的演变过程 一、 起初搭建整个大数据平台是基于CDH这一套资源管理和整合的CM资源管理器搭建的 整个平台包括了&#xff1a; HDFS&#xff0c;YARN&#xff0c;HIVE&#xff0c;zoozie,FLINK,Spark,Zookeeper等组件搭建而成&#xff0c; 刚开始搭建的时候&am…

Quartus II 13.1添加新的FPGA器件库

最近需要用到Altera的一款MAX II 系列EPM240的FPGA芯片&#xff0c;所以需要给我的Quartus II 13.1添加新的器件库&#xff0c;在此记录一下过程。 1 下载所需的期间库 进入Inter官网&#xff0c;&#xff08;Altera已经被Inter收购&#xff09;https://www.intel.cn/content…

人工智能导论-机器学习

机器学习概述 概述 本章主要介绍的机器学习的概念、发展历程、发展趋势、相关应用&#xff0c;着重拓展机监督学习和无监督学习的相关知识。 重点&#xff1a;机器学习的定义和应用&#xff1b; 难点&#xff1a;机器学习算法及分类。 机器学习 - 重要性 MachineLeaning出…

基于X86+FPGA+AI数字化医疗设备:全自动尿沉渣检测仪

助力数字医疗发展&#xff0c;信迈可提供全自动尿沉渣检测仪专用计算机 随着信息技术的不断进步&#xff0c;医疗也进入了一个全新的数字化时代。首先是医疗设备的数字化&#xff0c;大大丰富了医疗信息的内涵和容量&#xff0c;具有广阔的市场发展前景。 数字化医疗设备&…

[开源]语雀+Vercel:打造免费个人博客网站

大家好,我是白露。 今天我想和大家分享我的今年的第一个开源项目 —— 基于语雀+Nextjs+Vercel实现免费的博客系统。 简单来说,你在语雀写博客,然后直接一键同步到个人网站上,网站自动部署! 而且,整个过程几乎不需要额外的成本,也不用充值语雀超级会员,hh。这个项目…

IAR嵌入式开发解决方案已全面支持芯科集成CX3288系列车规RISC-V MCU,共同推动汽车高品质应用的安全开发

中国上海&#xff0c;2024年7月16日 — 全球领先的嵌入式系统开发软件解决方案供应商IAR与芯科集成电路&#xff08;以下简称“芯科集成”&#xff09;联合宣布&#xff0c;最新版本IAR Embedded Workbench for RISC-V 3.30.2功能安全版已全面支持芯科集成CX3288系列车规RISC-V…

分布式服务框架zookeeper+消息队列kafaka

一、zookeeper概述 zookeeper是一个分布式服务框架&#xff0c;它主要是用来解决分布式应用中经常遇到的一些数据管理问题&#xff0c;如&#xff1a;命名服务&#xff0c;状态同步&#xff0c;配置中心&#xff0c;集群管理等。 在分布式环境下&#xff0c;经常需要对应用/服…

秋招突击——7/18——多线程编程(Java线程池和Executor框架的)

文章目录 引言基础知识线程池原理Executor框架Executor框架的两级调度模型Executor框架结构Executor框架成员ThreadPoolExecutor详解——这里简单过一下&#xff0c;知道原理即可FixedThreadPool简介SingleThreadExecutorCachedThreadPool ScheduledThreadPoolExecutor详解——…

【Docker】基于Docker-compose创建LNMP环境

目录 一.Docker-compose 概述 1.容器编排管理与传统的容器管理的区别 2.docker-compose 作用 3.docker-compose 本质 4.docker-compose 的三大概念 二.YML文件格式及编写注意事项 1.yml文件是什么 2.yml问价使用注意事项 3.yml文件的基本数据结构 三.Docker-compose …

Redis常用的5大数据类型

Reids字符串&#xff08;String&#xff09; 设置相同的key&#xff0c;之前内容会覆盖掉 Redis列表&#xff08;List&#xff09; 常用命令 从左往右放值 数据结构 Redis集合&#xff08;set&#xff09; sadd<key><value1><value2>...... 数据结构 Set数据…

2024可信数据库发展大会|存算分离架构驱动电信数据平台革新

7 月 16 日 - 17 日&#xff0c;由中国通信标准化协会和中国信息通信研究院主办&#xff0c;大数据技术标准推进委员会承办&#xff0c;InfoQ 联合主办的「2024 可信数据库发展大会」&#xff08;TDBC&#xff09;在北京召开。 酷克数据解决方案架构师吴昊受邀参与“电信行业数…

给Wordpress评论列表的用户昵称增加个性化角色称号和注册年数

什么是个性化角色称号? 个性化称号:其实就是对应wordpress的几个用户组,重新给它装个面具。 比如:管理员 -> 华山掌门 比如:订阅者 -> 华山弟子 比如:VIP组 -> 掌门亲传弟子 。。。 就是个好玩的东西 什么又是注册年数? 显示用户在你的网站上注册了多少…

阿里布达插画:成都亚恒丰创教育科技有限公司

阿里布达插画&#xff1a;梦幻与现实交织的绮丽画卷 在浩瀚的艺术长河中&#xff0c;总有一些作品以其独特的魅力&#xff0c;跨越时空的界限&#xff0c;触动着每一个观者的心灵。阿里布达插画&#xff0c;便是这样一股不可忽视的艺术清流&#xff0c;它以细腻的情感描绘、奇…

紫光展锐5G安卓核心板T760__国产手机芯片方案

展锐T760安卓核心板是具备续航和性能更加均衡的5G移动平台。其主要特点包括主流的6400万像素摄像头和高达120Hz的刷新率。 平台采用多模融合的创新架构和AI智能调节技术&#xff0c;从而在5G数据场景下降低了37%的整体功耗&#xff0c;在5G待机场景下降低了18%的整体功耗。 多…

收银系统源码-线上商城diy装修

线下线上一体化收银系统越来越受门店重视&#xff0c;尤其是连锁多门店&#xff0c;想通过线下线上相互带动&#xff0c;相互引流&#xff0c;提升门店营业额。商城商城如何装修呢&#xff1f; 1.收银系统开发语言 核心开发语言: PHP、HTML5、Dart后台接口: PHP7.3后合管理网…

40.简易频率计(基于等精度测量法)(3)

&#xff08;1&#xff09;BCD8421码&#xff1a;十进制数字转换成BCD8421码的方法 补零&#xff1a;你需要显示多少位数字&#xff0c;就在前面补上四倍的位宽。比如你要显示一个十进制8位的数字&#xff0c;就在前面补上8*432个零。判断&#xff1a;判断补零部分显示的十进制…

2024717-VSCode-1.19.1-部署gcc13-C++23-win10-22h2

2024717-VSCode-1.19.1-部署gcc13-C++23-win10-22h2 一、软件环境 标签:C++ VSCode mingw gcc13分栏:C++操作系统:Windows10 x64 22h2二、操作步骤 1. 下载安装VScode 1.1官网 打开官网【https://code.visualstudio.com/Download】,选择【System Installer】【x64】,按…

一款由AI编写,简洁而实用的开源IP信息查看器

大家好&#xff0c;今天给大家分享一款用于查询和显示用户当前 IP 地址的轻量级项目MyIP。 MyIP提供了多种功能&#xff0c;包括IP地址查询、网络连通性检查、WebRTC连接检测、DNS泄露检查、网速测试、MTR测试等等。 使用MyIP&#xff0c;我们可以轻松地查看自己的公网IP地址&…

微软成为PostgreSQL主要贡献者

微软对PostgreSQL贡献的很多新功能都来自于客户在使用微软Azure上的PostgreSQL管理实例数据库&#xff0c;所以这些新功能都来自于真实的客户需求 微软贡献的这些新功能都是比较实用的功能 在这里&#xff0c;【真实的客户需求】要突出一下&#xff0c;因为现在很多社区贡献者…

电脑屏幕录制怎么弄?分享3个简单的电脑录屏方法

在信息爆炸的时代&#xff0c;屏幕上的每一个画面都可能成为我们生活中不可或缺的记忆。作为一名年轻男性&#xff0c;我对于录屏软件的需求可以说是既挑剔又实际。今天&#xff0c;我就为大家分享一下我近期体验的三款录屏软件&#xff1a;福昕录屏大师、转转大师录屏大师和OB…