堆优化 Dijkstra

一句话理解

堆优化 Dijkstra 用小根堆取最小 dist。

为什么要学

稀疏图。

讲解

允许同一点多次入堆，过期记录跳过。

例子

while (pq.size()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    // relax
}

懒惰删除。

常见错误

• decrease-key 自己手写错。
• 负权。