最短路，LeetCode 3112. 访问消失节点的最少时间

一、题目

1、题目描述

给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。

同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。

注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。

请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。

2、接口描述

python3

 ​

class Solution:def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:

cpp

 ​

class Solution {
public:vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {}
};

C#

 ​

public class Solution {public int[] MinimumTime(int n, int[][] edges, int[] disappear) {}
}

3、原题链接

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

---

二、解题报告

1、思路分析

最短路合集，Dijkstra，堆优化Dijkstra，BellmanFord，SPFA，Floyd，附完整代码及OJ链接-CSDN博客

就是dijkstra板子题

在松弛操作那里加一个disappear的判断即可

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(N)

3、代码详解

python3

 ​

class Solution:def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:pq = [(0, 0)]dst = [0] + [inf] * (n - 1)vis = [False] * ng = [[] for _ in range(n)]for u, v, w in edges:g[u].append((v, w))g[v].append((u, w))while pq:d, u = heappop(pq)if vis[u]:continuevis[u] = Truefor v, w in g[u]:if d + w < disappear[v] and d + w < dst[v]:dst[v] = d + wheappush(pq, (d + w, v))return [dst[i] if dst[i] < disappear[i] else -1 for i in range(n) ]

cpp

 ​

using PII = pair<int, int>;
class Solution {
public:vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {vector<vector<PII>> g(n);priority_queue<PII, vector<PII>, greater<PII>> pq;for (auto& e : edges) {g[e[0]].emplace_back(e[1], e[2]);g[e[1]].emplace_back(e[0], e[2]);}vector<bool> vis(n);vector<int> dst(n, 1e9 + 7);pq.emplace(dst[0] = 0, 0);while (pq.size()) {auto [d, u] = pq.top();pq.pop();if (vis[u]) continue;vis[u] = true;for (auto& [v, w] : g[u]) if (!vis[v] && d + w < min(dst[v], disappear[v])) pq.emplace(dst[v] = d + w, v);}vector<int> res(n);for (int i = 0; i < n; ++ i)res[i] = dst[i] < disappear[i] ? dst[i] : -1;return res;}
};

C#

 ​

public class Solution {public int[] MinimumTime(int n, int[][] edges, int[] disappear) {IList<int[]>[] adj = new IList<int[]>[n];for (int i = 0; i < n; i++) {adj[i] = new List<int[]>();}foreach (var e in edges) {adj[e[0]].Add(new int[]{e[1], e[2]});adj[e[1]].Add(new int[]{e[0], e[2]});}PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();pq.Enqueue(new int[]{0, 0}, 0);int[] res = new int[n];Array.Fill(res, -1);res[0] = 0;while (pq.Count > 0) {var t = pq.Dequeue();int d = t[0], u = t[1];if (d != res[u]) continue;foreach(var e in adj[u]) {int v = e[0], w = e[1];if ((res[v] == -1 || d + w < res[v]) && d + w < disappear[v]) {pq.Enqueue(new int[]{d + w, v}, d + w);res[v] = d + w;}}}return res;}
}