ABC61[D] score attack

Railsに追われていてC++を触れるような状況じゃなかったという言い訳もそこそこに、やっていきます。

D: Score Attack - AtCoder Beginner Contest 061 | AtCoder

ABC61D _WF_Score Attack

解説

この問題ではワーシャル・フロイド法がぎりぎりで通るため、それでやっていくのが賢い。（O(V^3)計算量のため、今回の制約V<=1000ではいわゆる”怪しい”ライン。とはいえ最低限の演算しかないために通るのだろうと思う）

ワーシャル・フロイドアルゴリズムはinit+三重ループだけで実装できる。アイデアはシンプルで、何かの経由点を取ったほうがいいかそうでないかを全点全関係においてループを回すというもの。隣接行列で使う方法で、隣接リストで使うやり方は知らない。多分無いかあったとしても回りくどいやり方になるのではないか。