Pachimon Creature(AOJ No.0215)

$x \times y$ のマップが与えられて、 1:火属性、 2:氷属性、 3:木属性、 4:土属性、 5:水属性のパチクリとスタート地点とゴール地点が配置されている。スタート地点で好きな属性のパチクリを貰って、全属性のパチクリを捕まえて、ゴール地点に到達するまでの最短距離と、そのときはじめに選んだパチクリの属性を求める。パチクリは、属性が...->1->2->3->4->5->1->...の順で捕まえることができる。この順になっていない場合は、素通りする。
制約
$2 \leq x,y \leq 1,000$
配置されるパチクリの数[0,1000]

アルゴリズム

最初のパチクリを選んだら、あとはDijkstraでゴールまでの最短距離を求める。要するに5回Dijkstraするだけ。距離はマンハッタン距離。

コード

memory limit exceededが出たので色々修正した。

import java.util.*;
public class aoj0215 {
	static final Scanner stdin = new Scanner(System.in);
	static final int INF = Integer.MAX_VALUE/2, TYPE = 5, ID = 0, DIST = 1;
	static class T {
		int y, x, id, type;
		T(int y, int x, int id, int type) { this.y = y; this.x = x; this.id = id; this.type = type;}
		int dist(T o) { return Math.abs(x - o.x) + Math.abs(y - o.y); }
	}
	public static void main(String[] args) {
		while (true) {
			int W = stdin.nextInt(), H = stdin.nextInt();
			if ((H|W) == 0) break;
			int id = 0;
			List<T> ref = new ArrayList<T>();
			List<List<T>> lists = new ArrayList<List<T>>();
			for (int i = 0; i < TYPE; ++i) lists.add(new ArrayList<T>());
			T  S = null, G = null;
			for (int i = 0; i < H; i++) {
				char[] line = stdin.next().toCharArray();
				for (int j = 0; j < W; j++) {
					switch (line[j]) {
					case 'S' : S = new T(i, j, id++, TYPE); ref.add(S); break;
					case 'G' : G = new T(i, j, id++, TYPE); ref.add(G); break;
					case '.' : break;
					default : 
						int type = line[j] - '1';
						T t = new T(i, j, id++, type);
						ref.add(t);
						lists.get(type).add(t);
						break;
					}
				}
			}
			
			int mType = -1, mDist = INF;
			for (int firstType = 0; firstType < TYPE; ++firstType) {
				S.type = firstType; G.type = (firstType + TYPE - 1) % TYPE;
				int dist = Dijkstra(ref, lists, S, G, id);
				if (dist < mDist) { mType = firstType + 1; mDist = dist; }
			}
			System.out.println(mDist < INF ? (mType + " " + mDist) : "NA");
		}
	}
	public static int Dijkstra(List<T> ref, List<List<T>> lists, T S, T G, int n){
		int[] dist = new int[n]; Arrays.fill(dist, INF);
		boolean[] visit = new boolean[n];
		Queue<int[]> q = new PriorityQueue<int[]>(n, new Comparator<int[]>() {
			@Override public int compare(int[] o1, int[] o2) { return o1[DIST] != o2[DIST] ? o1[DIST] - o2[DIST] : o1[ID] - o2[ID]; }
		});
		dist[S.id] = 0;
		q.add(new int[]{S.id, 0});
		while(!q.isEmpty()){
			int[] p = q.poll();
			T s = ref.get(p[ID]);
			if(visit[s.id]) continue;
			visit[s.id] = true;
			if (s.type == G.type) {
				int newDist = p[DIST] + s.dist(G);
				if(dist[G.id] > newDist){
					dist[G.id] = newDist;
					q.add(new int[]{ G.id, dist[G.id] });
				}
				continue;
			}
			for(final T d: lists.get((s.type+1)%TYPE)){
				int newDist = p[DIST] + s.dist(d);
				if(dist[d.id] > newDist){
					dist[d.id] = newDist;
					q.add(new int[]{ d.id, dist[d.id] });
				}
			}
		}
		return dist[G.id];
	}
}