AOJ : 0194 - Byakko Delivery Company
概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0194
日本語の問題文なので, 説明省略します.
ただし, 次のことに注意です.
問題文中に「交差点に到達した時刻に、信号が赤の場合には進入できません」と書いてあります.
これは, 本当に進入できないという意味で, 通行止めと同じ扱いになることに注意してください.
つまり, 「赤信号だから, その交差点で青になるまで待つ」ということはできないということです(サンプルを通してみればわかります).
アルゴリズム
ダイクストラ法で解きました.
各ノードを,
4 (現在向いている方向) * 100 (時間)
に分裂させて, ダイクストラを行います.
時間も含めているのは, それによって赤信号の状態が変化するためです.
プログラム
import java.util.*; import java.awt.Point; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int dx[] = {0,1,0,-1}; int dy[] = {-1,0,1,0}; boolean pass[] = {true,false,true,false}; while(true){ int h = sc.nextInt(); int w = sc.nextInt(); if(w == 0 && h == 0) break; int d = sc.nextInt(); //信号があるノードを記憶 HashMap<Point,Integer> node = new HashMap<Point,Integer>(); int ns = sc.nextInt(); for(int i=0;i<ns;i++){ node.put(toPoint(sc.next()),sc.nextInt()); } //通行止めのエッジを -1 のコストで記憶 HashMap<Point,HashMap<Point,Integer>> edge = new HashMap<Point,HashMap<Point,Integer>>(); int nc = sc.nextInt(); for(int i=0;i<nc;i++){ Point a = toPoint(sc.next()); Point b = toPoint(sc.next()); if(edge.get(a) == null) edge.put(a,new HashMap<Point,Integer>()); if(edge.get(b) == null) edge.put(b,new HashMap<Point,Integer>()); edge.get(a).put(b,-1); edge.get(b).put(a,-1); } //渋滞のエッジを渋滞の増分時間のコストで記憶 int nj = sc.nextInt(); for(int i=0;i<nj;i++){ Point a = toPoint(sc.next()); Point b = toPoint(sc.next()); int cost = sc.nextInt(); if(edge.get(a) == null) edge.put(a,new HashMap<Point,Integer>()); if(edge.get(b) == null) edge.put(b,new HashMap<Point,Integer>()); edge.get(a).put(b,cost); edge.get(b).put(a,cost); } Point start = toPoint(sc.next()); Point goal = toPoint(sc.next()); PriorityQueue<State> open = new PriorityQueue<State>(); HashSet<State> closed = new HashSet<State>(); open.add(new State(start,1,0)); State ans = null; while(!open.isEmpty()){ State st = open.poll(); if(closed.contains(st)) continue; closed.add(st); if(st.p.equals(goal)){ ans = st; break; } for(int i=0;i<4;i++){ //Uターンしてはいけない if((st.d + 2) % 4 == i) continue; Point np = new Point(st.p.x + dx[i], st.p.y + dy[i]); if(np.x>=0 && np.x<w && np.y>=0 && np.y<h){ int val = 0; //st.pからnpへの道情報を取り出す if(edge.containsKey(st.p) && edge.get(st.p).containsKey(np)) val = edge.get(st.p).get(np); //工事中なら通れない if(val == -1) continue; int ncost = st.cost + d + val; //信号がある場合の処理 if(node.containsKey(np)){ int k = node.get(np); boolean flg = pass[i]; //true:侵入可能である int div = ncost / k; if(div % 2 == 1) flg = !flg; if(!flg) continue; //ちょうど青でなければ通れない } open.add(new State(np,i,ncost)); } } } System.out.println(ans.cost); } } private static Point toPoint(String s){ String[] tmp = s.split("-"); int x = Integer.parseInt(tmp[1]) - 1; int y = tmp[0].charAt(0) - 'a'; return new Point(x,y); } } class State implements Comparable<State>{ Point p; int d,cost; State(Point p,int d,int cost){ this.p = new Point(p.x,p.y); this.d = d; this.cost = cost; } public int compareTo(State st){ return this.cost - st.cost; } public boolean equals(Object o){ State st = (State)o; return p.equals(st.p) && d == st.d && cost == st.cost; } public int hashCode(){ return p.x + 100 * p.y + d * 10000 + 100000 * cost; } }