全点対間最短路問題フロイド・ワーシャル法で解ける問題に挑戦してみました。 atcoder.jp 書いたPythonコード n_knuuさんのscipyで書かれたACコードを元に勉強がてら。 これコード見ても、何気にムズイ感じがする。 L以下の経路をばっさり切ってbooleanに変…

scipyが気に入ったので、scipyの別アルゴリズムで解ける問題を順次やっていきます。 atcoder.jp Pythonコード 解説で説明されている実装を、キレイにscipyのmaximum_flowで実装しているn_knuuさんのコードがあったので、それを元に書く。 まぁ、ほぼ一緒だけ…

scipyのダイクストラの使い方を覚えたので、ダイクストラで解けるAtCoderの別問題に挑戦してみました。 atcoder.jp 書いたPythonコード return_predecessors = True で経路が返ってくる (デフォルトはFalse) とのことで、これをつけてdijkstraを呼び出し。 i…

最短経路問題はAtCoderで良く出てますが、まだ解いたことないのでやってみることにしました。 まずは代表的な最短経路問題用アルゴリズムであるダイクストラ法から解いてみようと。 しかし、最近のAtCoderの問題だとだいぶヒネリが効いてるだろう。 なるべく…