AOJ 0601 - フクロモモンガ(JOI2013本戦4)

フクロモモンガ | Aizu Online Judge
提出コード
けんちょんさんのブログに載っていたため解いたのですが、DP！と思って問題を読んでみたらむしろダイクストラ法の問題だな、という感想でした。条件がそこそこ複雑だったので、配列の要素を変数でいちいち置きなおしてたのですが、逆に読みづらいなぁと思いました。

それでは解法のメモです。
priority_queueで、ある木に行くまでにかかる時間をソートしながらダイクストラ法をしていきます。まず初めに、入力を受け取るときにそれぞれの木ごとに、そこから行くことのできる別の木と移動にかかる時間のセットを記録します。
続いて、ダイクストラ法を記録する配列を用意します。とある木にたどり着くまでの時間の最小値と、そのときの高さをメモします。
いよいよ、ダイクストラ法をするのですが、考えるべきパターンは4つあります。

1. 現在の高さのまま次の頂点に飛ぶと、次の木の高さをオーバーしてしまう場合

この場合は、次の木の頂点にたどりつくことができるように、現在の木で少し降りてから飛びます。このとき、次の木に移動するまでの時間は
(現在の高さ)-(次の木の頂点の高さ)
になります。そして、そのときの高さは
(次の木の頂点の高さ)
になります。

2. 現在の高さから飛ぶと、次の木にちょうどたどり着ける場合

次の木にそのまま飛び移ればいいので、移動時間は
(現在の木から次の木までの移動にかかる時間)
となります。そしてそのときの高さは
(現在の高さ)-(移動にかかる時間)
になります。

3. 現在の高さから飛ぶと、地面に埋もれてしまう場合

少し木をのぼってから移動しなければなりませんので、最低限だけのぼることを考えると、移動にかかる時間は
(現在の木から次の木までの移動にかかる時間)×2-(現在の高さ)
となります。そしてそのときの高さは
0
になります。

4. そもそも現在の木の頂点から飛んでも、地面に埋もれてしまう場合

移動できないので、スルーします。

これで、次の高さと、移動する合計時間が算出できました。
あとはこれを次の頂点の部分にメモして、priority_queueに格納していけば、答えが求まります。