【LeetCode:3112. 访问消失节点的最少时间 + Dijkstra】

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

🚩 题目链接

• 3112. 访问消失节点的最少时间

⛲ 题目描述

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

🥦 求解思路

1. 此题t通过Dijkstra算法求解，唯一的区别是在将当前节点的邻接点 v 放入堆时，还需要判断新的路径长度是否小于等于 disappear[v]，如果不满足，则不入堆。其他步骤与迪杰斯特拉算法一致。
2. 有了基本的思路，接下来我们就来通过代码来实现一下的解法。

🥦 实现代码

class Solution {public int[] minimumTime(int n, int[][] edges, int[] disappear) {List<int[]>[] g = new ArrayList[n];Arrays.setAll(g, i -> new ArrayList<>());for (int[] e : edges) {int x = e[0];int y = e[1];int weight = e[2];g[x].add(new int[] { y, weight });g[y].add(new int[] { x, weight });}int[] dis = new int[n];Arrays.fill(dis, -1);dis[0] = 0;PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));pq.offer(new int[] { 0, 0 });while (!pq.isEmpty()) {int[] temp = pq.poll();int distance = temp[0];int node = temp[1];if (distance > dis[node]) {continue;}for (int[] next : g[node]) {int y = next[0];int newDistance = distance + next[1];if (newDistance < disappear[y] && (dis[y] < 0 || newDistance < dis[y])) {dis[y] = newDistance;pq.offer(new int[] { newDistance, y });}}}return dis;}
}

🥦 运行结果

---

💬 共勉

最后，我想和大家分享一句一直激励我的座右铭，希望可以与大家共勉！