問題
atcoder.jp
解法
フロイドワーシャルとかライブラリ叩けば良いんじゃね？と思ってたんだが、この問題で求められてる処理自体がフロイドワーシャルのアルゴリズムそのものですよ。
というアルゴリズム教養問題だった。
なるほど、こういう処理なのね。
経由地を順繰りに追加していって、その経由地を通るルートが最短ルートでないか比較していく。
そうかー、知らんかった。
実装
はまやん氏のCの実装をPythonにコンバート。
ワーシャルフロイドって、こういう処理だったのかぁ。
実行結果
PyPy3(7.3.0) AC 2827ms
Python(3.8.2) TLE
Pythonの方は、ダメかー。
参考
blog.hamayanhamayan.com
