Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12047 - Highest Paid Toll (この記事を編集する[管理者用])

Source

Next generation Contest 6 (2011-06-25)
UVa 12047

問題概要

ノード数10000以下,枝数100000以下の有向グラフが与えられる.枝にはコスト (0以上10^5以下) が付けられている.
始点と終点が与えられる.
支点から終点に移動する総コストがp以下パスの中に含まれる1本の枝のコストの最大値を最大化したい.
最大値を求める問題.

解法

各枝について,その枝を使って,始点から終点までコストp以下でいけるかを判定すればいい.
それは,始点からダイクストラ,終点から枝の向きを逆にしてダイクストラしておくことで,各枝について,
 この枝にたどり着くまでのコスト + この枝のコスト + この枝から終点にたどり着くまでのコスト
でこの枝を通る最小コストが計算できるようになる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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