Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1054-63901960
この記事にトラックバックする(FC2ブログユーザー)

Aizu 2042 - So Sleepy (この記事を編集する[管理者用])

Source

ICPC OB/OG会 模擬地区予選2007 (2007-10-21)
Aizu 2042

問題概要

駅の数は1000個以下,路線の数は100個以下.
それぞれの路線は同じ駅は高々1個しか含まず,各駅に止まる時刻が決まっている.
出発する駅,出発する時刻,到着する駅,到着すべき時間が与えられるので,最も長い時間乗っている電車の時間を最大化する問題.
最大値のみを求める.

解法

ダイクストラっぽく,最初からある駅に辿り着ける最も早い時間と,この時間にこの駅にいても到着できる最も遅い時間を求めておく.
すると,各路線の各駅間に対して,それを乗っても出発地から目的地に辿りつけるかすぐ判定できる.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1054-63901960
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。