42 · 最短路：Dijkstra 与 Floyd

① dist 的定义和 BFS 一样。dist[v] 表示“当前已知的 s 到 v 最短距离”。dist[s] = 0，其余设成一个极大的数 INF。注意是极大，不是 0 —— 全 0 等于宣布“所有点都已经到达且距离为 0”，后面一条边都松弛不动。

② 重复做一件事：取出未确定的点里 dist 最小的那个 u，用它松弛所有出边。“松弛”就是三角不等式：if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;。BFS 里这一步是 dist[v] = dist[u] + 1，因为不用比也知道更优。

③ 为什么取最小就能“确定”。假设弹出的 u 的 dist 还不是真正的最短距离 d(u)。在 s→u 的真实最短路上，从 s 开始找第一个还没被确定的点 y。y 之前的点都已确定并松弛过，所以 dist[y] = d(y)。因为边权非负，最短路越往后越长，所以 d(y) ≤ d(u)；又因为 u 是当前未确定点里 dist 最小的，所以 dist[u] ≤ dist[y]。串起来：d(y) ≤ d(u) < dist[u] ≤ dist[y] = d(y)，矛盾。∎ “边权非负”只用在这一步，这是全节最值得记住的一句话。

④ 用堆代替线性扫描。朴素写法每次在 n 个点里找最小是 O(n²)；把 (dist, u) 丢进小根堆，top() 就是最小，代价 O(log n)。

⑤ 懒删除。priority_queue 不能改已入堆的值，也不能删任意元素，所以 dist 变小时就再 push 一份新的，旧记录留在堆里。取出时判断 if (d != dist[u]) continue; —— 对不上说明这条是过期记录，扔掉。

⑥ 复杂度。每条边最多触发一次 push，所以最多 push m + 1 次；堆大小 ≤ m + 1；每次 push/pop 是 O(log m)。总复杂度 O((n + m) log m)，写成 O((n + m) log n) 也一样。

// 骨架：初始化 → 源点入堆 → 弹堆顶 → 懒删除 → 松弛 → 新值入堆
vector<long long> dist(n + 1, INF);
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue;                 // 过期记录，扔掉
    for (auto &e : g[u]) {                      // 只扫 u 的出边，每条边一生只被扫一次
        int v = e.first, w = e.second;
        if (dist[u] + w < dist[v]) {            // 三角不等式
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});              // 新值入堆，旧值不管
        }
    }
}

Dijkstra 解决“一个源点到所有点”。如果要所有点对的距离，跑 n 次 Dijkstra 是 O(n(m + n) log n)，n = 500 时约 8.5×10⁸，太慢；而 Floyd 是 O(n³) = 1.25×10⁸，反而更快。稠密图上，Floyd 常常是更优的选择。

思路是动态规划。定义 f_k(i, j) = 只允许把编号 1..k 的点当作中转点时，i 到 j 的最短距离。从 k−1 推到 k 只有两种选择：不用 k，还是 f_k−1(i, j)；用 k，就是 f_k−1(i, k) + f_k−1(k, j)。于是

f_k(i, j) = min( f_k−1(i, j), f_k−1(i, k) + f_k−1(k, j) )。

k 这一维可以滚掉：算 f_k 时 f_k−1(i, k) 与 f_k−1(k, j) 的值和 f_k 的那两个值相同（最短路经过 k 本身不会变得更短，除非有负环），所以直接就地覆盖成二维数组即可。这就是为什么 k 循环必须写最外层 —— 它是 DP 的阶段维。

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

const int N = 305;
const long long INF = (long long)4e18;
long long f[N][N];

int main() {
    int n, m;                      // n ≤ 300
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            f[i][j] = (i == j ? 0 : INF);          // ★ 自己到自己是 0
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        f[u][v] = min(f[u][v], (long long)w);      // 重边取最小
    }
    for (int k = 1; k <= n; ++k)                   // ★ 阶段：必须最外层
        for (int i = 1; i <= n; ++i) {
            if (f[i][k] == INF) continue;          // 剪枝：i 到不了 k，这一层白算
            for (int j = 1; j <= n; ++j)
                if (f[i][k] + f[k][j] < f[i][j])
                    f[i][j] = f[i][k] + f[k][j];
        }
    // 到这里 f[i][j] 就是 i 到 j 的最短路
}

k 放里层会错，给一个具体反例。4 个点、3 条边 1→3、3→4、4→2，权都是 1，正确答案 d(1, 2) = 3。若写成 for i for j for k：算 (i = 1, j = 2) 时需要用 f[1][4]，而 f[1][4]（要等 j = 4 才算）此刻还是 INF，于是 f[1][2] 永远停在 INF。这类错误的表现是“一部分点对正确、一部分是 INF 或偏大”，极难靠小样例发现。

Floyd 还白送三件东西：①允许负权边（只要没有负环）；②判负环 —— 跑完看 f[i][i] < 0，说明有负环（正常应该等于 0）；③传递闭包 —— 把 min 换成 or、+ 换成 and，得到的就是“i 能否走到 j”，三重循环一个字不用改。

给一个三点反例，能一次看清问题：边 1→2 权 2，1→3 权 5，3→2 权 −4。真实答案是 d(2) = 1（绕 3 号点走）。Dijkstra 的执行顺序是：dist = [0, 2, 5]，先弹出 2 号点（dist = 2 最小），把它当最终值；再弹出 3 号点，松弛 3→2 得到 1 —— 但 2 号点已经处理完了，答案停在 2。这一段描述的是带“弹出即确定”标记的经典实现（弹出后 vis[u] = true 并不再更新 u），本节代码没有这个标记，结论见第三段。

坏在哪一步？回到前面的证明：那句 d(y) ≤ d(u) 用的是“最短路越往后越长”，而这条性质只在边权非负时成立。有负边时，最短路可能越走越短，“先取出的最小点”就不再是确定的。

还要说清楚一个细节，很多资料含糊过去：本节这种“懒删除、不加 vis”的写法，在负权图上最终仍会给出正确答案，因为每次距离变小都会重新入堆，等价于堆版的 Bellman-Ford —— 但复杂度从 O((n + m) log n) 退化成 O(nm) 量级，SPFA 的卡法能把它卡死。而只要你为了提速加上“弹出即确定”（if (vis[u]) continue; vis[u] = true;），负权图上就是彻底的 WA。

所以结论不变，只是理由更精确：Dijkstra 的复杂度保证依赖非负权，正确性在带“确定”标记的实现里也依赖它。有负权边时用 Bellman-Ford / SPFA，并且用它顺手判负环。

最后一个容易忽视的推论：无向图里只要出现一条负权边，就一定有负环（这条边来回走一趟，总权变成负数，可以无限刷小），此时最短路根本不存在。所以看到“无向图 + 负边”要么题目保证没有，要么答案是 −∞，不要指望任何最短路算法给出有限值。