Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12680 - Shopping Malls (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12680

問題概要

ショッピングモール中の $N$ 個の施設とその場所(何階にあるかと $x,y$ 座標)が与えられる.各フロア間の距離は $5$ m で,$x,y$ の単位は m.
施設間に移動する方法が $M$ 個与えられる.
それぞれの移動方法は $2$ つの施設間を移動でき,以下の $4$ 種類がある.
 walking または stairs:歩く距離は $2$ つの施設間のユークリッド距離(walkingとstairsの違いは施設が同じフロアにあるかどうかのみ)
 lift:歩く距離は $1$ mで移動できる
 escalator:順方向には $1$ mで移動でき,逆方向には,施設間のユークリッド距離の $3$ 倍歩けば移動できる.
クエリが $Q$ 個与えられる.
各クエリでは,施設 $a$ から $b$ に移動する方法のうち,最小の歩く距離で移動する方法を出力する.
たぶん移動方法は一意に定まるか,複数の最適解があればどれを出力しても良いと思われる.
全ての施設間で移動する方法があることは保証されている.
$N \leq 200$
$M \leq 1000$
$Q \leq 1000$

解法

各クエリごとにダイクストラして経路復元する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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