AOJ 2585 - 一日乗車券

問題
提出コード

解法

• 1日乗り放題になる路線をビットで表したものがとなるようにする際の、1Dayパスポートの合計金額の最小値

をまず求めます。
これは、配るDPを用いて、を繰り返し計算していけばよいです。で求まります。
では、乗り放題の路線を決め打ちしてとした際の、からへ行く方法の中で、金額が最小になるものを調べます。
これは、

• 時間後ににいるような行き方のなかでの金額の最小値

とすると、グラフを拡張してダイクストラ法を使ってあげれば、が答えになります。
初期値は、です。
これを全ての状態について調べ、その最小値を求めれば答えが求まります。

感想

はじめ、が24以下であると勘違いして、間に合わないなぁ…って言ってました。状態が少し複雑になるだけでバグを埋め込みやすいので、バグ少なめでかけた点についてはよかったです。