AOJ2135 Reverse a Road

問題リンク Reverse a Road

• 概要

1〜Nまでの番号がついた街と、M本の有向路(番号1〜M)がある。街SからTまでの最短距離を求めよ。
ただし、M本の辺のうち1本だけ向きを逆向きにすることができる。最短距離を得るために変えた辺の番号も答えよ。そのような辺が複数ある場合は最も番号が小さいものを答えよ。辺を逆向きにせずに最短距離が得られた場合は番号として0を答えよ。

• 解法

愚直に全探索して解きました。
逆向きにする辺を全て選び、その都度幅優先探索をします。幅優先探索中、最短距離を更新できないことがわかったら探索を打ち切ります。
もっと賢い工夫を考えなければ解けないと思っていましたが、これで通ってしまいました。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

//Reverse a Road
public class AOJ2135 {

	class E{
		int id, t;
		public E(int id, int t) {
			this.id = id;
			this.t = t;
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		int INF = 1<<29;
		int[] d = new int[1001];
		int[][] e = new int[10001][2];
		List<E>[] adj = new List[1001];
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			for(int i=1;i<=n;i++)adj[i]=new ArrayList<E>();
			int S = sc.nextInt(), T = sc.nextInt(), m = sc.nextInt();
			for(int i=1;i<=m;i++){
				int s = sc.nextInt(), t = sc.nextInt();
				adj[s].add(new E(i, t));
				e[i][0] = s; e[i][1] = t;
			}
			Arrays.fill(d, INF);
			d[S] = 0;
			Queue<Integer> q = new LinkedList<Integer>();
			q.add(S);
			while(!q.isEmpty()){
				int v = q.poll();
				for(E r:adj[v])if(d[r.t]==INF){
					d[r.t] = d[v]+1; q.add(r.t);
				}
			}
			int res = d[T], ID = 0;
			for(int i=1;i<=m;i++){
				Arrays.fill(d, INF);
				d[S] = 0;
				q = new LinkedList<Integer>();
				q.add(S);
				int rs = e[i][1], rt = e[i][0];
				while(!q.isEmpty()){
					int v = q.poll();
					if(res<=d[v])break;
					for(E r:adj[v])if(r.id!=i&&d[r.t]==INF){
						d[r.t] = d[v]+1; q.add(r.t);
					}
					if(v==rs&&d[rt]==INF){
						d[rt] = d[v]+1; q.add(rt);
					}
				}
				if(d[T]<res){
					res = d[T]; ID = i;
				}
			}
			System.out.println(res+" "+ID);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2135().run();
	}
}