AOJ 2021 - お姫様の危機
解法
町の数が少ないので、まずは任意の2つの町を結ぶ最短経路を求めます。これは、ワーシャルフロイドを利用すれば簡単に求めることができます。
あとは、スタート地点から、今いる地点から分以内で行ける、冷凍施設のある町のみを経由してゴールの町まで行くことができるかどうか、そしてその場合の最短経路を調べます。これは、ダイクストラ法を利用することで求めることができます。このとき求まった最短経路を
とします。
最後に、途中で冷凍する時間を追加してあげます。
最初の町にいる時点では、分間冷やさなくても大丈夫です。また、
の場合は、目的地に着いた時点で、ちょうど残り時間が0になるようにするのが最適です。
これらを踏まえると、結局は
が求める答えになります。
感想
ワーシャルフロイドとダイクストラを組み合わせる系問題でした(ダイクストラは2回目のワーシャルフロイドでも問題ない気もします)。この手の問題の考察をぱぱぱーっと解くことができると、昔よりは強くなったな、という気分になれます。
制約と、最短距離を求めたい雰囲気が出ている時点で、これらの手法が使いたくなりますね。
