blog主に競プロ問題の解説を載せてますこの広告は、90日以上更新していないブログに表示しています。DangerAOJpythonで粘ったがTLEから逃れられなかった。深いループの中で四則演算するとどうにもならない。問題はこちらN個と都市間を結ぶM本の双方向道路があり、道路によって結ばれた都市は時間Tiで行き来できる。今都市Aにいて、都市Hに冷凍された血液を冷凍されたまま運びたいのだが、血液はある程度時間がたつと溶けてしまう。N個の都市のうちL個は冷凍施設を持っており、血液を再度冷凍することができる。はじめ血液は時間Mだけ溶けずにいることができ、冷凍施設では冷凍に使った時間分だけ血液の解けずにいられる時間が伸びる(ただし最大Mまで)。これらの条件のもと都市Aから都市Hまで無事に血液を運ぶことができるかどうか、できるなら運ぶのにかかる最短の時間を答える。解法いくつか解き方があるようだが、ダイクストラを用いた方法とワーシャル・フロイドを用いた方法に分かれるようだ。自分はワーシャル・フロイドを用いた方法で解いた。ワーシャル・フロイドを適用して都市間の距離を計算する。大切なのは冷凍施設のある都市で、はじめ都市Aから出発し、距離M以下で都市Hに到達できる都市に行きつくまで、距離M以下の冷凍施設のある都市を巡っていけばいい。ある都市と都市H間の移動時間を2次元配列に代入してワーシャルフロイドを行えば、都市Aと都市Hまでの最短時間を計算できる。あとはこの時間tがINF以上ならHelp!を、INF以下ならMを超えるかどうかチェックし、越えていたらt-Mを足し加えればいい(適当な都市で再冷凍を行ったことにする)。読者になるリンクTopCoderCodeforcestwitterGitHubQiitaはてなブログをはじめよう!roiti46さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。