AOJ 0601 - フクロモモンガ (Sugar Glider)

Source

第13回日本情報オリンピック本選 4問目
AOJ 0601

問題概要

木が $N$ 本あって,$i$ 番目の木の高さ $H_i$ が与えられる.
木 $i$ では高さ $0$ から $H_i$ までの場所にいることができる.
高さ $1$ だけ昇り降りするのにかかる時間は $1$ である.
また,$M$ 個の木のペア $(A_i,B_i)$ が与えられて,そのペアの木間をジャンプして移動するのにかかる時間 $T_i$ が与えられる.
ジャンプ中は時間 $1$ につき,高さが $1$ だけ減少する.
つまり,その間を,高さ $h$ からジャンプして移動すると,到着地点は高さ $h-T_i$ となる.
これが,到着地点の木の高さより高かったり,地面より下の場合は,ジャンプ不可能.
今,木 $1$ の高さ $X$ の地点にいる.
木 $N$ の頂上に辿り着くまでの最小時間を求める問題.

解法

基本的には,それぞれの木に移動するための最小ジャンプ時間を求めるダイクストラ.
木 $k$ に到着するまでのジャンプ時間が $X - h_k$ 未満だったら,木を下がらなければいけないが,それは無駄にジャンプしたことにして,$X - h_k$ のジャンプ時間でたどり着けると解釈すれば良い.
また,$T_i$ が今いる木の高さより大きければ,そのジャンプは不可能なことに注意.
後は,最短ジャンプ時間から,必要時間を適当に割り出せば良い.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年09月21日05時13分12秒
Last modified: 2015年03月31日08時27分15秒 (by laycrs)
Tags: Competitive_Programming Aizu_Online_Judge JOI_2014
トップページに戻る

Logged in as: unknown user (not login)

ログイン: