Hos' Xmas Contest 2011 B "shortest path"

問題:http://atcoder.jp/problem/detail/133

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt(), m = s.nextInt();
		long d = s.nextInt();
		int st = s.nextInt(), ed = s.nextInt();
		Map<Integer, List<int[]>> map = new HashMap<Integer, List<int[]>>();
		for (int i = 0; i < m; ++i) {
			int u = s.nextInt(), v = s.nextInt(), c = s.nextInt();
			List<int[]> list1 = map.get(u);
			if (list1 == null) {
				list1 = new ArrayList<int[]>();
			}
			list1.add(new int[] { v, c });
			map.put(u, list1);
			List<int[]> list2 = map.get(v);
			if (list2 == null) {
				list2 = new ArrayList<int[]>();
			}
			list2.add(new int[] { u, c });
			map.put(v, list2);
		}
		PriorityQueue<long[]> q = new PriorityQueue<long[]>(10, new Comparator<long[]>() {
			@Override
			public int compare(long[] o1, long[] o2) {
				return Double.compare(o1[2], o2[2]);
			}
		});
		q.add(new long[] { -1, st, 0 });
		boolean[] b = new boolean[n];
		while (!q.isEmpty()) {
			long[] p = q.poll();
			if (p[1] == ed) {
				System.out.println(p[2]);
				return;
			}
			if (p[0] >= 0) {
				b[(int) p[0]] = true;
			}
			if (p[1] > 0 && !b[(int) p[1]]) {
				q.add(new long[] { p[1], p[1] - 1, p[2] + d });
			}
			if (p[1] < n - 1 && !b[(int) p[1]]) {
				q.add(new long[] { p[1], p[1] + 1, p[2] + d });
			}
			List<int[]> list = map.get((int) p[1]);
			if (list != null) {
				for (int[] x : list) {
					if (!b[x[0]]) {
						q.add(new long[] { p[1], x[0], p[2] + x[1] });
					}
				}
			}
		}
		System.out.println();
	}

	static class Scanner {
		java.io.BufferedInputStream bis;

		public Scanner(java.io.InputStream is) {
			bis = new java.io.BufferedInputStream(is);
		}

		public String next() {
			StringBuilder sb = new StringBuilder();
			int b = ' ';
			try {
				for (; Character.isWhitespace(b); b = bis.read())
					;
				for (; !Character.isWhitespace(b); b = bis.read()) {
					sb.append((char) b);
				}
			} catch (Exception e) {
				e.printStackTrace();
			}
			return sb.toString();
		}

		public int nextInt() {
			int r = 0, s = 1, b = ' ';
			try {
				for (; Character.isWhitespace(b); b = bis.read())
					;
				if ((s = b == '-' ? -1 : 1) < 0) {
					b = bis.read();
				}
				for (; Character.isDigit(b); b = bis.read())
					r = r * 10 + b - '0';
			} catch (Exception e) {
			}
			return s * r;

		}
	}

}