2015-02-10から1日間の記事一覧

AOJ 2021: お姫様の危機をワーシャル-フロイト法で解く

問題 Princess in Danger | Aizu Online Judge 解法 まずは制限時間や冷凍庫位置を考えずに、ワーシャルフロイト法で任意の2点間の最小必要時間を出しておく。すると任意の2冷凍庫間の最小必要時間も出る。この後は冷凍庫間の移動だけを考えるので、それ以外…

AOJ 1127: クラスカル法で最小全域木問題を解く

問題 Building a Space Station | Aizu Online Judge 3次元空間にn個の球形の宇宙ステーションがあるので、それらを行き来する通路を作る際の、通路の最小合計距離を求める。 解法 2つの宇宙ステーション間の距離を求め、最小全域木探索する。 コード import…