弗洛伊德算法需三层循环，k为最外层中转点；核心是disti = min(disti, disti + distk)；初始化disti=0、无边为大数（如1e18）；可检测负环（disti<0）；推荐用long long防溢出。
弗洛伊德算法用 floyd_warshall 实现最稳
直接上手就是三层循环：外层是中转点 k，内层是起点 i 和终点 j。核心逻辑只有一行：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。别把 k 放错位置——它必须是**最外层循环**，否则无法保证中转点逐步“解锁”，结果会错。
常见错误现象：dist[i][j] 值没变、出现负数但没报错、部分路径比实际长。本质是中转点顺序混乱，或初始化不全。
- 初始化时，
dist[i][i]必须设为0；无边连接的点对设为一个足够大的数（如INT_MAX/2），不能用INT_MAX直接加，否则溢出变负 - 图必须用邻接矩阵存，稀疏图也得转——虽然空间浪费，但算法逻辑依赖
O(1)查边 - 如果要记录路径，额外开
next[i][j]存第一个中转点，每次更新dist时同步更新next
检测负权环只需多加一行判断
弗洛伊德本身能顺带揪出负权环：跑完三重循环后，检查任意 dist[i][i] < 0 即可。注意不是看 dist[i][j] 是否变小，而是看对角线——因为 dist[i][i] 表示从 i 出发回到 i 的最短路，正常应为 0，若小于 0 就说明存在负环。
- 别在循环中途 break：必须完整跑完
k从0到n-1才能确保所有中转组合被覆盖 - 一旦发现
dist[i][i] < 0，整个距离矩阵已不可信，后续查询无意义 - 某些实现用
dist[i][i] == -1标记负环，这是自定义约定，标准做法还是比0
int 还是 long long？看边权范围和点数
溢出是弗洛伊德最隐蔽的坑。比如 n=500，边权最大 1e6，理论上最长路径可能达 499 * 1e6 ≈ 5e8，int 还撑得住；但若边权含负数且绝对值大，或 n 上千，int 很快在 dist[i][k] + dist[k][j] 这步溢出，变成负数，干扰负环判断甚至让最短路计算崩溃。
立即学习“C++免费学习笔记（深入）”；
- 保守起见，统一用
long long，尤其当输入边权类型是long long或题目没说范围时 - 初始化“无穷大”别写死
0x3f3f3f3f——那是为int设计的；改用LLONG_MAX / 3或自定义常量如const long long INF = 1e18 - 编译器对
INT_MAX + 1是未定义行为，不是简单截断，所以宁可多算一点空间，别省这点类型转换
求路径而非仅长度？next 数组比递归重建更可靠
想输出 i 到 j 的具体路径，靠每次查 dist 回溯容易漏节点。标准解法是维护 next[i][j]：初始时若 i→j 有边，next[i][j] = j；更新 dist[i][j] 时，若经 k 更短，则 next[i][j] = next[i][k]。
- 还原路径用迭代：从
i开始，while (i != j) { path.push_back(i); i = next[i][j]; }，最后补上j - 注意
next[i][j]在dist[i][j]更新时才更新，不是每次循环都赋值 - 如果
dist[i][j]仍是 INF，next[i][j]无意义，使用前必须先判连通性
实际写的时候，最容易被忽略的是初始化时对角线和无穷大的取值平衡——太小会误判负环，太大在加法中溢出，这个边界感得靠几次 WA 来调准。
