当前位置：首页 > 力扣 > 力扣3112题解法：带时间限制的最短路径问题解析（C++代码）

力扣3112题解法：带时间限制的最短路径问题解析（C++代码）

3周前 (06-25)

一、题目解读

力扣3112题要求解决带时间限制的最短路径问题：给定一个有向图，节点具有消失时间，需计算从起点到各节点的最短路径，且路径总时间不能超过节点的消失时间。题目难点在于需在传统最短路径算法（如Dijkstra）中融入时间窗口判断，确保到达节点时未“消失”。此外，需处理无法到达的节点并标记为-1。

二、解题思路

1. 核心思想：采用Dijkstra算法框架，结合时间限制优化。通过优先队列维护“当前时间+节点”的最小堆，确保每次扩展最短路径的节点。

2. 关键步骤：

构建邻接表存储带权边（节点+时间）。

初始化距离数组，起点为0，其余INT_MAX。

优先队列按时间排序，避免超时节点扩散。

遍历邻接边时，判断新时间是否满足“未超时且更优”，更新距离并入队。

3. 优化点：

跳过已超时节点（time > dist[u]），减少无效计算。

无法到达节点标记为-1，避免INT_MAX误导。

三、解题步骤

1. 构建图结构：使用vector<pair<int, int>>构建邻接表，存储双向边（u→v, t时间）。

2. 初始化：距离数组dist初始化为INT_MAX，起点dist[0]=0；优先队列pq加入(0, 0)。

3. 主循环：

弹出堆顶(time, u)，若time已超时（>dist[u]），跳过。

遍历u的邻接节点(v, t)：计算新时间new_time = time + t。

若new_time < disappear[v]（未超时）且更优，更新dist[v]并入队。

4. 后处理：将dist中仍为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;
    }
};

注释说明：

● 邻接表双向存储节省时间复杂度。

● 优先队列按时间排序，确保扩展顺序正确。

● 超时判断避免无效路径扩散，提升效率。

● 最终标记不可达节点满足题目要求。