Analysis: Classical problem, calculate the shortest paths between every nodes. Use Floyd's algorithm, the time complexity O(n^3).
The trick is for the large data set, if we create an array of dimension [80000][80000], it is either too slow or take too much space. Notice the limitation of the room color, there are no more than (26+10)*(26+10) + (26+10) colors, if we calculate the shortest distance in the color space instead of the room number space, the problem is reduced to compute an array of no more than [1400][1400] (1332 would be more accurate).
package codeJam.google.com;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
/**
* @author Zhenyi 2013 Dec 22, 2013 16:18:30 PM
*/
public class SpaceshipDefence {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new
FileReader("C:/Users/Zhenyi/Downloads/E-small-practice.in"));
FileWriter out = new
FileWriter("C:/Users/Zhenyi/Downloads/E-small-practice.out");
// BufferedReader in = new BufferedReader(new FileReader(
// "C:/Users/Zhenyi/Downloads/E-large-practice.in"));
// FileWriter out = new FileWriter(
// "C:/Users/Zhenyi/Downloads/E-large-practice.out");
int T = new Integer(in.readLine());
for (int cases = 1; cases <= T; cases++) {
int N = new Integer(in.readLine());
int[] roomColor = new int[N];
int[][] shortestDist = new int[1400][1400];
for (int i = 0; i < 1400; i++) {
for (int j = 0; j < 1400; j++) {
shortestDist[i][j] = Integer.MAX_VALUE;
if (i == j)
shortestDist[i][j] = 0;
}
}
HashMap
colorMap = new HashMap
(); for (int i = 0; i < N; i++) { String st = in.readLine(); if (!colorMap.containsKey(st)) { int t = colorMap.size(); colorMap.put(st, t); } roomColor[i] = colorMap.get(st); } Integer M = new Integer(in.readLine()); for (int i = 0; i < M; i++) { String[] st = in.readLine().split("\\s"); Integer a = new Integer(st[0]) - 1; Integer b = new Integer(st[1]) - 1; Integer value = new Integer(st[2]); if (shortestDist[roomColor[a]][roomColor[b]] > value) { shortestDist[roomColor[a]][roomColor[b]] = value; } } for (int k = 0; k <= colorMap.size(); k++) { for (int i = 0; i <= colorMap.size(); i++) { for (int j = 0; j <= colorMap.size(); j++) { if (shortestDist[i][k] != Integer.MAX_VALUE && shortestDist[k][j] != Integer.MAX_VALUE && shortestDist[i][k] + shortestDist[k][j] < shortestDist[i][j]) { shortestDist[i][j] = shortestDist[i][k] + shortestDist[k][j]; } } } } Integer s = new Integer(in.readLine()); out.write("Case #" + cases + ":\n"); for (int i = 0; i < s; i++) { String[] st = in.readLine().split("\\s"); Integer start = new Integer(st[0]) - 1; Integer end = new Integer(st[1]) - 1; int result = shortestDist[roomColor[start]][roomColor[end]]; if (result == Integer.MAX_VALUE) { result = -1; } out.write(result + "\n"); } } in.close(); out.flush(); out.close(); } }