ワーシャルフロイド簡単やん!と思ったら落とし穴 (abc079_d)

Quiz

https://atcoder.jp/contests/abc079/tasks/abc079_d

Submit

https://atcoder.jp/contests/abc079/submissions/3888526

落とし穴

  • 最初はforをi, j, kの順に書き、i->j->kと経由を想定して書いたら、提出後に部分的にWA
    • サンプルで通ってしまうのが怖い・・・
  • ワーシャルフロイドは一番外側のforを経由点とするように書く必要があった

ワーシャルフロイドとは?

  • グラフ問題で各頂点から各頂点への最短距離を求める
  • ノード数Vとして、計算量はO(V3)
FOR(i, 0, 10){ // 経由点
    FOR(j, 0, 10){ // 始点
        FOR(k, 0, 10){ // 終点
            c[j][k] = min(c[j][k], c[j][i] + c[i][k]);
        }
    }
}