pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

dwango2016-prelims.contest.atcoder.jp

解法

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

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

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

  • (出発点から現在地点までの移動時間)+(終点までの移動時間)+(終点から目的地までの最短移動時間)

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


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

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