ワーシャルフロイド法で解ける問題 AtCoder Beginner Contest 143 [ E - Travel by Car ] をscipyのfloyd_warshallで解く
全点対間最短路問題フロイド・ワーシャル法で解ける問題に挑戦してみました。
書いたPythonコード
n_knuuさんのscipyで書かれたACコードを元に勉強がてら。
これコード見ても、何気にムズイ感じがする。
L以下の経路をばっさり切ってbooleanに変換するところが、「途中で補給できる場合もあるんだから、バッサリ切ってよいの？」と思ってしまうが、途中で補給して到達できる街への経路は、最後のfloyd_warshallの呼び出しで正しく考慮される。
そこが直感的に分かりづらいと思うんだが、正しい答えが出るってことは、これであってんのね。
[結果]
Python(3.8.2) AC 448ms
