ワーシャルフロイド法 - 一人で始めるプログラミング

こんにちは。Arkです。

最近はC問題が解けるようになってきたので、D問題に挑戦してみようと適当にとってきた問題がこちらです。

まず一目見て、なんだこれっ！！ってなりました。図形問題でやったことあるのDFSだけだし、かといってDFSも自分で実装できないしな～～って感じだったので少し考えてすぐに解説を見ました。（天才が考えたことを僕は勉強するだけです...）

まず、解説の最初の文にワーシャルフロイド法という名前が出てくるも、初耳すぎて頭の中が　?(・ω・)?　という感じでした。そこで調べて自分で実装してみました。

僕なりにまとめるとこんな感じ。(カッコ内は僕のコードにおける行番号を示す)

①頂点間の移動距離を0で初期化（16）

②自己連結の場合はそのまま0にし、他の頂点とつなげる場合はINF(=∞)にする（19）

③入力で得られた頂点間にパスがつながっている場合、そこのINFを上書きする（22）

④頂点i から頂点j に行く移動距離と、頂点i から頂点k を経由して頂点j に行く移動距離を比べ、小さい方を頂点i~頂点j の移動距離として上書きする(29)←この操作がワーシャルフロイド法におけるもっとも重要な部分！！！

⑤next_permutationを使うためにソートし、最短経路を出力する(34~41)

以上こんな感じです。最後のnext_permutationは数学のコンビネーション(nCr)のようなものです。これはまた記事にしたいなと思っています。にしてもD問題ってこんな方法を知らないと解けない問題とかが多そうなので、これからも精進あるのみだと感じました。

競プロを初めて今日で5週間がたちましたが、最初はB問題でさえ解けなかったのがよくここまで来たなという感じです。精進みを感じることが出来て僕は結構満足しています。しかし、上には上がいるので日々精進を忘れることなく頑張ります！！！！！

(2019/5/17追記)

AtCorder Beginner Contest 079-Dでも似たような問題があり、一発ACをすることが出来てうれしいので追記しておきます。

問題

解答

いや、自分天才では？？？

完