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