floyd算法核心是k在最外层的三重循环，初始化用int_max/2防溢出，负环检测通过disti
Floyd算法的核心实现就三重循环，别写错k的位置
标准Floyd的三层循环顺序必须是 k 在最外层，i 和 j 在内层。如果把 i 或 j 放最外层，结果大概率是错的——它会漏掉某些中间节点的松弛路径。
-
k表示“当前允许经过的中间节点编号”，必须从 0 到 n-1 依次枚举，保证每轮都扩展一个新中转点 - 内层
i、j遍历所有点对，检查是否能通过k缩短距离：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) - 初始化时，
dist[i][i]设为 0，有边的设为对应权重，无边的设为一个足够大的数（如INT_MAX/2，避免加法溢出）
INT_MAX 直接用会溢出，得用 INT_MAX/2 或 LLONG_MAX/2
当图里存在 INT_MAX 表示的“无穷大”，两个 INT_MAX 相加会整数溢出，变成负数，后续比较就全乱了。这不是理论风险，是实际跑几组数据就能复现的 bug。
- 推荐初始化为
INT_MAX / 2（int类型）或LLONG_MAX / 2（long long类型） - 不要用
-1或0x3f3f3f3f混用——前者无法参与min()正常比较，后者在 64 位下可能不够大 - 判断不可达时，别写
if (dist[i][j] == INT_MAX)，要写if (dist[i][j] > INF / 2)，其中INF是你定义的上限值
检测负环只需在 Floyd 结束后加一行判断
Floyd 本身不显式报错负环，但跑完后只要发现任意 dist[i][i] ，就说明从 <code>i 出发存在负权回路。这是最直接、开销最小的检测方式。
- 不需要额外跑一遍循环，就在三重循环之后立刻加：
for (int i = 0; i - 注意：有些实现会跳过
i == k或j == k的情况，但检测负环必须看对角线dist[i][i]，不能省 - 如果只关心最短路，不关心负环，这步可省；但一旦输入图可能含负权边，这行就得加上，否则结果无意义
空间复杂度 O(n²)，但二维数组别用 vector> 动态套娃
频繁访问二维 vector 的 dist[i][j]，比原生 int dist[N][N] 或 vector<int> dist(N * N)</int> 慢不少，尤其在 n 较大（比如 500+）时明显卡。
立即学习“C++免费学习笔记（深入）”；
- 优先用一维模拟二维：
dist[i * n + j]，连续内存，cache 友好 - 若必须用 vector，至少声明为
vector<vector>> dist(n, vector<int>(n))</int></vector>，别在循环里反复push_back - 编译器对
int dist[500][500]的优化很成熟，只要 n 确定且不太大（≤1000），栈上分配也完全可行
Floyd 看似简单，但 k 循环位置、无穷大取值、负环检测时机、内存布局这四点，任一出错都会导致结果错误或运行异常——它们不是边缘情况，而是日常调试里最常卡住的地方。
