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

Medium

题目描述

有一个包含 n 个节点的无向图。给你一个二维数组 edges，其中 edges[i] = [ui, vi, lengthi] 描述了节点 ui 和节点 vi 之间的一条边，遍历时间为 lengthi 个单位。

另外，给你一个数组 disappear，其中 disappear[i] 表示节点 i 从图中消失的时间，你将无法访问它。

注意，图可能是不连通的，并且可能包含多条边。

返回数组 answer，其中 answer[i] 表示从节点 0 到达节点 i 所需的最少时间单位。如果节点 i 从节点 0 无法到达，则 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]

示例 3：

输入：n = 2, edges = [[0,1,1]], disappear = [1,1]
输出：[0,-1]

约束条件：

1 <= n <= 5 * 10^4
0 <= edges.length <= 10^5
edges[i] == [ui, vi, lengthi]
0 <= ui, vi <= n - 1
1 <= lengthi <= 10^5
disappear.length == n
1 <= disappear[i] <= 10^5

解题思路

这是一个带时间约束的最短路径问题，需要使用Dijkstra算法的变种来解决。

核心思路：

图的构建：根据edges数组构建邻接表表示的无向图
Dijkstra算法：使用优先队列（最小堆）来找到从节点0到所有其他节点的最短路径
时间约束：关键是在访问每个节点时检查是否在该节点消失之前到达

算法步骤：

构建图的邻接表
初始化距离数组，所有节点距离设为无穷大，起点设为0
使用优先队列存储 (距离, 节点) 对，按距离从小到大排序
对于队列中的每个节点：
- 如果当前距离大于已知最短距离，跳过（已处理过更优路径）
- 遍历所有邻居节点，计算新距离
- 如果新距离小于邻居的已知距离且小于邻居的消失时间，更新距离并加入队列

时间复杂度考虑：

每个节点最多被处理一次
每条边最多被松弛一次
优先队列操作的复杂度为O(log V)

这种方法确保我们找到的是在时间约束内的真正最短路径。

代码实现

class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        
        vector<int> dist(n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        dist[0] = 0;
        pq.push({0, 0});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto [v, w] : graph[u]) {
                int newDist = dist[u] + w;
                if (newDist < dist[v] && newDist < disappear[v]) {
                    dist[v] = newDist;
                    pq.push({newDist, v});
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (dist[i] == INT_MAX) {
                dist[i] = -1;
            }
        }
        
        return dist;
    }
};

class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        import heapq
        
        graph = [[] for _ in range(n)]
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        dist = [float('inf')] * n
        dist[0] = 0
        pq = [(0, 0)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            if d > dist[u]:
                continue
            
            for v, w in graph[u]:
                new_dist = dist[u] + w
                if new_dist < dist[v] and new_dist < disappear[v]:
                    dist[v] = new_dist
                    heapq.heappush(pq, (new_dist, v))
        
        return [-1 if d == float('inf') else d for d in dist]

public class Solution {
    public int[] MinimumTime(int n, int[][] edges, int[] disappear) {
        var graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].Add((v, w));
            graph[v].Add((u, w));
        }
        
        var dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[0] = 0;
        
        var pq = new PriorityQueue<(int dist, int node), int>();
        pq.Enqueue((0, 0), 0);
        
        while (pq.Count > 0) {
            var (d, u) = pq.Dequeue();
            
            if (d > dist[u]) continue;
            
            foreach (var (v, w) in graph[u]) {
                int newDist = dist[u] + w;
                if (newDist < dist[v] && newDist < disappear[v]) {
                    dist[v] = newDist;
                    pq.Enqueue((newDist, v), newDist);
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (dist[i] == int.MaxValue) {
                dist[i] = -1;
            }
        }
        
        return dist;
    }
}

var minimumTime = function(n, edges, disappear) {
    const graph = Array.from({length: n}, () => []);
    
    for (const [u, v, length] of edges) {
        graph[u].push([v, length]);
        graph[v].push([u, length]);
    }
    
    const dist = new Array(n).fill(Infinity);
    dist[0] = 0;
    
    const pq = [[0, 0]];
    
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [d, u] = pq.shift();
        
        if (d > dist[u]) continue;
        
        for (const [v, length] of graph[u]) {
            const newDist = dist[u] + length;
            if (newDist < dist[v] && newDist < disappear[v]) {
                dist[v] = newDist;
                pq.push([newDist, v]);
            }
        }
    }
    
    return dist.map(d => d === Infinity ? -1 : d);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构建图	O(E)	O(V + E)
Dijkstra算法	O((V + E) log V)	O(V)
总体	O((V + E) log V)	O(V + E)

其中 V = n 是节点数，E = edges.length 是边数。

时间复杂度：O((V + E) log V)，每个节点最多入队出队一次，每次队列操作需要 O(log V)
空间复杂度：O(V + E)，主要用于存储图的邻接表和优先队列

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目