Document

Turn Left
原案：阿部
担当：福澤, 笠原
英訳：寺島
解説：福澤
問題１
 車で移動して京都観光をすることにしたタロー君たち
でも免許を持っているのはタローくんだけです！
さらにタローくんは右折ができません！
 直進と左折だけで目的地へ行ける最短経路を求め，
最短経路が通る最小交差点数を出力せよ
問題２
烏丸丸太町河原町丸太町
Sample Inputの３つ目
烏丸五条から川端御池への経路探索
烏丸五条 → 四条烏丸 →
烏丸御池 → 堀川御池 →
堀川四条 → 四条烏丸 →
四条河原町 → 河原町御池 →
河原町丸太町 → 烏丸丸太町 →
烏丸御池 → 河原町御池 →
川端御池
通る交差点数１３
二度通る交差点
四条烏丸，烏丸御池，河原町御池）
烏丸御池
川端御池
河原町御池
堀川御池
四条烏丸四条河原町
堀川四条
烏丸五条
問題条件
 通りは南北または東西方向に延びている
 全ての通りは両方向とも通れる
 同一座標に複数の交差点は無い
 通り同士は与えられた交差点以外で交差しない
 通りの間に別の交差点は無い
 通りの重複区間は無い
 交差点の最大数1000
 以上の条件から通り数は最大でも1935
解法
 ダイクストラ法
 グラフを交差点と交差点へ進入した向きの組合せに拡大して構築
 拡大したグラフの上でダイクストラを行う
 計算量
疎なグラフに対するダイクストラ法の計算量 (E + V) log V
 V = 交差点数 * 隣接する交差点数 = 4K
 Vの頂点の最大字数は4なので，E = 2V = 8K
 (E+V) log V = 140K

注意点
 左折のみではありません．
タロー君は直進もできます！
 求めるものは，最短経路の中の最小交差点数です！
結果
 Submit数
：
 Accepted数
：
 First Submit
：
 First Accepted ：
19
5
77分
157分（ Makegumi )

Download Report