堆优化 Dijkstra 复习速记

目标：考前快速复习、快速背模板、快速排错。
关键词：非负边权、单源最短路、小根堆、松弛。

---

1. 用来解决什么？

Dijkstra：求一个起点到所有点的最短路。

适用条件：

所有边权 >= 0

不能处理：

负权边

---

2. 核心思想

每次从还没确定的点里，选一个当前距离起点最近的点，把它的最短路确定下来。

堆优化就是用 小根堆 快速找到这个点。

流程：

起点入堆
每次弹出 dist 最小的点 u
如果 u 已经确定，跳过
否则确定 u
用 u 去更新相邻点 v
如果 dist[v] 变短，就更新并重新入堆

---

3. 必背变量

struct Edge {
    int to, w;
};

vector<Edge> g[N]; // 邻接表
int dist[N];       // 起点到每个点的最短距离
bool vis[N];       // 这个点的最短路是否已经确定

堆里存：

{距离, 点编号}

所以写：

pq.push({dist[v], v});

---

4. 最重要的松弛

对于边：

u -> v，边权 w

如果经过 u 到 v 更短：

if (dist[v] > dist[u] + w) {
    dist[v] = dist[u] + w;
    pq.push({dist[v], v});
}

记住：

最短路：能变小，就更新。

---

5. 标准模板 int 版

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;
const int INF = 0x3f3f3f3f;

int n, m;
int dist[N];
bool vis[N];

struct Edge {
    int to, w;
};

vector<Edge> g[N];

void dijkstra(int s) {
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (auto e : g[u]) {
            int v = e.to;
            int w = e.w;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;

        // 无向图
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    dijkstra(1);

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }

    return 0;
}

---

6. long long 版怎么改？

如果边权大、路径长，改成 long long。

主要改这几个地方：

const long long INF = 4e18;
long long dist[N];

struct Edge {
    int to;
    long long w;
};

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

其余逻辑不变。

---

7. 有向图 / 无向图

有向图：

g[a].push_back({b, c});

无向图：

g[a].push_back({b, c});
g[b].push_back({a, c});

---

8. 为什么要 vis？

因为同一个点可能多次入堆。

比如堆里可能同时有：

{100, v}
{50, v}
{20, v}

最先弹出 {20, v}，此时 v 的最短路确定。

后面的 {50, v}、{100, v} 都是旧状态，要跳过：

if (vis[u]) continue;

---

9. 时间复杂度

常用记法：

O(m log n)

更严谨地说，普通 priority_queue 懒删除写法中，堆里可能有 O(m) 个元素，所以也可以写：

O(m log m)

但简单图中：

m <= n^2
log m <= 2 log n

所以竞赛里通常写：

O(m log n)

空间复杂度：

O(n + m)

---

10. 为什么堆操作是 log？

priority_queue 底层是二叉堆。

堆有 k 个元素时，高度约为：

log k

push 可能从底往上调整，pop 可能从顶往下调整，最多走一条高度。

所以：

push / pop = O(log k)

---

11. 不能处理负权边的原因

Dijkstra 每次会确定当前最近的点。

如果有负权边，后面可能通过负边让已经确定的点变得更短。

所以负权边会破坏 Dijkstra 的正确性。

---

12. 考前检查清单

[ ] 边权是否全部非负
[ ] 是否使用邻接表 vector<Edge>
[ ] Edge 是否是 to, w
[ ] 小根堆是否写了 greater<pair<int,int>>
[ ] 堆里是否存 {距离, 点}
[ ] dist 是否初始化为 INF
[ ] 起点 dist[s] 是否为 0
[ ] 是否写 if (vis[u]) continue
[ ] 是否写 vis[u] = true
[ ] 松弛条件是否是 dist[v] > dist[u] + w
[ ] 更新后是否重新入堆
[ ] 无向图是否加双向边
[ ] 答案大时是否使用 long long
[ ] 不可达点是否输出 INF

---

13. 最后只背这几句

Dijkstra 用于非负边权单源最短路。
堆里存 {距离, 点}，用小根堆。
每次弹出当前距离最小的点。
访问过就跳过，没访问就确定。
枚举出边，能让 dist 变小就松弛。
复杂度常记 O(m log n)。

最核心代码：

if (dist[v] > dist[u] + w) {
    dist[v] = dist[u] + w;
    pq.push({dist[v], v});
}