LeetCode 3112题深度剖析：时间约束下的路径规划

一、问题重述

我们需要在考虑节点消失时间限制的无向图中，计算从节点0到所有其他节点的最短到达时间。如果无法在节点消失前到达，则返回-1。

二、算法选择

这个问题适合使用Dijkstra算法，因为：

1. 我们需要单源最短路径

2. 所有边权非负（时间必须为正）

3. 需要处理额外的约束条件（节点消失时间）

三、关键实现细节

1. 图表示

使用邻接表存储图结构，可以高效地遍历每个节点的邻接边。对于无向图，每条边需要在邻接表中存储两次。

2. 优先队列优化

使用最小堆实现的优先队列来选择当前距离最短的节点进行处理，这是Dijkstra算法的核心优化。

3. 消失时间处理

在松弛边时，增加对目标节点消失时间的检查：

• 只有新计算的时间小于目标节点的消失时间才考虑更新

• 同时也要小于当前记录的最短时间

4. 结果初始化与处理

• 初始时所有节点距离设为INT_MAX（不可达）

• 节点0的距离设为0

• 最后将仍为INT_MAX的值设为-1表示不可达

四、实现代码

class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        // 构建邻接表
    vector<vector<pair<int, int>>> graph(n);
    for (const auto& edge : edges) {
        int u = edge[0], v = edge[1], t = edge[2];
        graph[u].emplace_back(v, t);
        graph[v].emplace_back(u, t);
    }
   
    // 初始化距离数组
    vector<int> dist(n, INT_MAX);
    dist[0] = 0;
   
    // 最小堆，存储(到达时间, 节点)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.emplace(0, 0);
   
    while (!pq.empty()) {
        auto [time, u] = pq.top();
        pq.pop();
       
        // 如果当前时间已经超过记录的最短时间，跳过
        if (time > dist[u]) continue;
       
        // 遍历所有邻接节点
        for (const auto& [v, t] : graph[u]) {
            int new_time = time + t;
           
            // 检查是否能在节点消失前到达
            if (new_time < disappear[v] && new_time < dist[v]) {
                dist[v] = new_time;
                pq.emplace(new_time, v);
            }
        }
    }
   
    // 处理无法到达的节点
    for (int i = 0; i < n; ++i) {
        if (dist[i] == INT_MAX) {
            dist[i] = -1;
        }
    }
   
    return dist;
    }
};

五、复杂度分析

• 时间复杂度：O(E + VlogV)

• 构建邻接表：O(E)

• 优先队列操作：每个节点最多入队一次，每次操作O(logV)

• 空间复杂度：O(V + E)

• 邻接表存储：O(E)

• 距离数组：O(V)

• 优先队列：最坏O(V)

六、边界情况考虑

1. 节点0自身消失时间为0的情况

2. 图不连通的情况

3. 多条边连接同一对节点的情况

4. 节点消失时间非常小，导致大多数节点无法到达的情况

参考：力扣3112题解：