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; } } }