力扣3112题解法：带时间限制的最短路径问题解析（C++代码）
一、题目解读
力扣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;
}
};注释说明：
● 邻接表双向存储节省时间复杂度。
● 优先队列按时间排序，确保扩展顺序正确。
● 超时判断避免无效路径扩散，提升效率。
● 最终标记不可达节点满足题目要求。
五、总结
本文解法通过融合Dijkstra算法与严格的时间窗口判断，高效解决了力扣3112题。关键点在于：
1. 优先队列维护时间顺序，避免超时节点污染结果。
2. 邻接表双向存储适应无向图特性，降低代码复杂度。
3. 明确标记不可达节点，符合题目输出要求。
该思路适用于有时间限制的最短路径问题，对算法优化与逻辑严谨性有较高要求，为同类题目提供通用解法模板。
原创内容 转载请注明出处
