Floyd

一句话理解

Floyd：三重循环，任意点对最短路。

为什么要学

n≤400。

讲解

for k for i for j 松弛 i->k->j。k 必须在最外。

例子

for (int k = 1; k <= n; k++)
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

k 是允许使用的中间点编号上限。

常见错误

• k 不在最外。
• 没把无边设 inf，0 会乱传。