ワーシャルフロイド簡単やん!と思ったら落とし穴 (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を経由点とするように書く必要があった

最短経路の本 レナのふしぎな数学の旅

最短経路の本 レナのふしぎな数学の旅

  • 作者: P.グリッツマン,R.ブランデンベルク,石田基広
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/04/05
  • メディア: 単行本(ソフトカバー)
  • クリック: 1回
  • この商品を含むブログを見る

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

  • グラフ問題で各頂点から各頂点への最短距離を求める
  • ノード数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]);
            }
        }
    }