ワーシャルフロイド法 - 個人的な競プロメモ

ワーシャルフロイド法

全点対間最短路を求めるアルゴリズムの一つ

計算量は$ O(N^3)

簡潔に書ける

DP

Warshall–Floydって書いたりする

ちなみにDPなので(?)負閉路も検出できます。ループ回してから、dp[i][i]が0より小さいかで分かります。

AOJでの実装例