Warshall-Floyd の本質ミス

ミス

o rep(k,N) rep(i,N) rep(j,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]);
x rep(i,N) rep(j,N) rep(k,N) d[i][j] = d[j][i] = min(d[i][j],d[i][k]+d[k][j]);

なぜか

Warshall-Floydの証明を考えれば明らか.
証明
Warshall-Floydが何をしているかというと,最初のループがk回終わった時点で, V_k = {0,.. ,k-1} を経由点とする最短路を全て求めている.
これによって帰納法により全点最短経路が求められる.
逆に,そうしなければ正しく最短路が求められない.

メモ

1行で書けるので毎回書いてたけど,間違えて覚えたらしい.
ハマった.