Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11814 - Stack Machine (この記事を編集する[管理者用])

Source

Waterloo Local Summer 2010 (2010-07-11)
UVa 11814

問題概要

ノード数100以下,枝数100000以下の有向グラフが与えられる.
枝には絶対値が40以上220以下の整数のラベルが付けられている.
クエリが100000個以下与えられて,あるノードからあるノードに移動する,以下の条件を満たす,正の長さのパスのうちもっとも短いものの長さを求める問題.
最初と最後はスタックが空で,ラベルが正の枝を通過したとき,スタックにその数字を積む.ラベルが負の枝が,ラベルの絶対値がスタックの最後に積まれてないと移動できず,移動するとスタックの最後の要素を消す.
枝の長さは全部1.

解法

(開始ノード, 終了ノード)の組を状態としてBFSする.
例えば,A→Bまで長さKで行けるなら,+Lの枝と-Lの枝を使って,
 A→B→C→D (A→Dは長さK+2でいける)
 C→D→A→B (C→Bは長さK+2でいける)
 C→A→B→D (C→Dは長さK+2でいける)
という感じに更新していく.
ラベルがlong long 3個に押し込めるので,bit演算などを使った.それでもO(100^4)だと思うのだけど,実行時間は大してかからず通った.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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