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]); } } }