floyd-warshall核心是三重循环：外层k从0到n-1，内层i、j遍历所有点，更新disti = min(disti, disti + distk)；k顺序不可颠倒，否则破坏动态规划正确性。
Floyd-Warshall 算法在 C++ 中不是“调用库函数”，而是手动实现三重循环更新距离矩阵；它适合顶点数 ≤ 500 的稠密图，超了容易 TLE 或溢出。
怎么写核心三重循环（dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])）
这是算法唯一必须写的逻辑，顺序不能错：最外层是中转点 k，内层是起点 i 和终点 j。如果把 k 放在最内层，结果会错——因为此时 dist[i][k] 和 dist[k][j] 还没被前序 k 更新过，无法保证“只经编号 ≤ k 的点”的动态规划含义。
-
k必须从0到n-1递增枚举（不是任意顺序） - 初始化时，
dist[i][i]设为0，无边位置设为一个足够大但不溢出的值，比如0x3f3f3f3f（约 10⁹），别用INT_MAX—— 加法会溢出变成负数 - 如果有重边，读入时用
min(dist[u][v], w)取最小权重，别直接覆盖
怎么检测负环（dist[i][i] ）
Floyd 结束后，检查任意 dist[i][i] 是否小于 0。只要有一个成立，说明存在从 i 出发又回到 i 的负权环，此时所有经过该环的路径都无最短路（可无限绕圈减小总权）。注意：这个判断必须在三重循环全部执行完之后做，不能边更新边检查。
- 不要只检查
dist[0][0]，要遍历所有i - 一旦发现
dist[i][i] ，后续 <code>dist[i][j]值已不可信，不应再用于业务逻辑 - 有些题要求“输出任意负环上的点”，这时需额外记录
next[i][j]数组并回溯路径
怎么还原任意两点最短路径（不只是距离）
单纯求距离只需 dist 二维数组；若还要输出路径本身，得维护一个 next[i][j] 表示从 i 到 j 的最短路上，i 的下一个点是谁。初始化时 next[i][j] = j（直连），更新 dist[i][j] 时同步更新 next[i][j] = next[i][k]。
- 还原路径用递归或迭代：从
i开始，不断取next[i][j]直到等于j - 注意：如果
dist[i][j]仍是初始大值，说明不可达，next[i][j]无意义 - 空间开销翻倍，且不能省略初始化 —— 否则
next[i][j]是垃圾值
常见编译/运行错误和踩坑点
实际写的时候最容易栽在数据范围与初始化上，而不是逻辑本身。
-
dist数组用int但边权总和可能超2e9？改用long long并把 INF 设为0x3f3f3f3f3f3f3f3fLL - 输入点数
n后，忘了给dist分配n×n空间，或下标越界访问（C++ 中vector<vector>> dist(n, vector<int>(n))</int></vector>更安全） - 图是有向图，但误把
dist[u][v] = dist[v][u] = w—— 这会把有向图当无向图处理 - 没处理自环：输入含
u == v且w ，直接导致初始化就出现 <code>dist[i][i] ，提前触发负环判定
真正麻烦的从来不是三重循环本身，而是 INF 的选值、负环的语义判断时机、以及路径还原时 next 数组的边界条件 —— 这些地方一错，整个结果就静默失效，很难调试。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
