AOJ 2005: Water Pipe Construction
問題
Water Pipe Construction | Aizu Online Judge
解法
ある点tについて、min{(sからtまでの最短距離) + (tからg1までの最短距離) + (tからg2までの最短距離)}が求めるべき答えなので、tを全探索。
全点対最短距離を求めるのはワーシャルフロイドでもなんでもいい。
import java.util.*; import java.io.*; import java.awt.geom.*; import java.math.*; public class AOJ2005 { static final Scanner in = new Scanner(System.in); static final PrintWriter out = new PrintWriter(System.out,false); static boolean debug = false; public static int[][][] directedGraph(int n, int[] s, int[] t, int[] cost) { int[] cnt = new int[n]; for (int i : s) cnt[i]++; int[][][] g = new int[n][][]; for (int i=0; i<n; i++) g[i] = new int[cnt[i]][2]; for (int i=0; i<s.length; i++) { int from = s[i]; int to = t[i]; g[from][--cnt[from]][0] = to; g[from][cnt[from]][1] = cost[i]; } return g; } public static long[] dijkstra(int[][][] g, int source) { int n = g.length; final long[] d = new long[n]; Arrays.fill(d, Integer.MAX_VALUE/2); d[source] = 0; TreeSet<Integer> pQ = new TreeSet<Integer>(new Comparator<Integer>(){ public int compare(Integer a, Integer b) { if (d[a] != d[b]) return d[a] > d[b] ? 1 : -1; return a > b ? 1 : -1; } }); pQ.add(source); while (!pQ.isEmpty()) { int cur = pQ.pollFirst(); for (int i=0; i<g[cur].length; i++) { int next = g[cur][i][0]; long dist = d[cur] + g[cur][i][1]; if (dist < d[next]) { pQ.remove(next); d[next] = dist; pQ.add(next); } } } return d; } static boolean solve() { int n = in.nextInt(); int m = in.nextInt(); int s = in.nextInt() - 1; int g1 = in.nextInt() - 1; int g2 = in.nextInt() - 1; if (n + m == 0) return false; int[] v1 = new int[m]; int[] v2 = new int[m]; int[] c = new int[m]; for (int i=0; i<m; i++) { v1[i] = in.nextInt() - 1; v2[i] = in.nextInt() - 1; c[i] = in.nextInt(); } int[][][] g = directedGraph(n, v1, v2, c); long[] ds = dijkstra(g, s); long ans = ds[g1] + ds[g2]; for (int i=0; i<n; i++) { if (i == s) continue; long[] d = dijkstra(g, i); ans = Math.min(ans, ds[i] + d[g1] + d[g2]); } out.println(ans); return true; } public static void main(String[] args) { debug = args.length > 0; long start = System.currentTimeMillis(); while(solve()); out.flush(); long end = System.currentTimeMillis(); dump((end-start) + "ms"); in.close(); out.close(); } static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); } }