第2回ドワンゴからの挑戦状予選 C - メンテナンス明け

移動先・移動時間・終点・終点までの移動時間の情報を持った辺でグラフを構成する。

「目的地に移動時間 x 以下でたどり着けるか」で二分探索をする。

ある辺を通っている最中に寝てしまった場合、最終的な移動時間は

に確定する。もしこれが x を越えていたらこの辺は使えず、越えていなかったら何の問題もなく使える。よって寝たら x を越えてしまう辺を使わないようにダイクストラ法をして判定すればいい。

二分探索すると辺の制約が簡単になるの面白い。