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