AOJ - Problem 0189 : Convenient Location

ConvenientLocation.java

/**
 * @author Taketo Yoshida
 */
import java.util.*;
 
public class ConvenientLocation {
  private Solver solver;

  public class Pair<F, S> {
    private F first; //first member of pair
    private S second; //second member of pair
    public Pair(F first, S second) {
      this.first = first;
      this.second = second;
    }
    public void setFirst(F first) { this.first = first; }
    public void setSecond(S second) { this.second = second; }
    public F getFirst() { return first; }
    public S getSecond() { return second; }
    public boolean eq(Pair<?, ?> p) {
      return first.equals(p.getFirst()) && second.equals(p.getSecond());
    }
    public String toString() { return first.toString() + ", " + second.toString();}
  }
 
  interface Solver {
    public Pair<Integer, Integer> solve(int[][] cost, int N);
  }
 
  class FwSolver implements Solver {
    private final int MAX = Integer.MAX_VALUE/10;
    /** 
     * @param cost adjacency matrix of cost
     * @param N number of city
     * @return answer pair(city_number, distance)
     */
    public Pair<Integer, Integer> solve(int[][] cost, int N) {
      for (int k = 0; k < N; k++) 
        for (int i = 0; i < N; i++)
          for (int j = 0; j < N; j++) 
            cost[i][j] = Math.min(cost[i][j],
                cost[i][k]+cost[k][j]);

      int ansCity = 0;
      int ansDist = MAX;
      for (int i = 0; i < N; i++) {
        int dist = 0;
        for (int j = 0; j < N; j++) 
          dist += cost[i][j];
        if (ansDist > dist) {
          ansDist = dist;
          ansCity = i;
        }
      }
      return new Pair<Integer, Integer>(ansCity, ansDist);
    }
  }
 
  public ConvenientLocation() {
    solver = new FwSolver();
  }
 
  public static void main(String[] args) {
    int testCase = -1;
    double start = System.currentTimeMillis();
    (new ConvenientLocation()).runTest(testCase);
    double end = System.currentTimeMillis();
    System.out.println("time : " + (end - start) + "ms");
  }
 
  public void runTest(int testCase) {
    if ((testCase == -1) || (testCase == 0)) testCase0();
    if ((testCase == -1) || (testCase == 1)) testCase1();
    if ((testCase == -1) || (testCase == 2)) testCase2();
  }
 
  private void verifyCase(int testCase, Pair<Integer, Integer> expected, Pair<Integer, Integer> received) {
    System.err.println("Test Case #" + testCase + "...");
    if (expected.eq(received)) {
      System.err.println("PASSED"); 
    } else { 
      System.err.println("FAILED"); 
      System.err.println("\tExpected: \"" + expected + '\"');
      System.err.println("\tReceived: \"" + received + '\"');
    }
  }
 
  private void testCase0() {
    int max = Integer.MAX_VALUE/10;
    int[][] Arr0 = {
      {0, 1, max, max, max, max, max, max, max, max},
      {1, 0, 1, max, max, max, max, max, max, max},
      {max, 1, 0, max, max, max, max, max, max, max},
      {max, max, max, 0, max, max, max, max, max, max},
      {max, max, max, max, 0, max, max, max, max, max},
      {max, max, max, max, max, 0, max, max, max, max},
      {max, max, max, max, max, max, 0, max, max, max},
      {max, max, max, max, max, max, max, 0, max, max},
      {max, max, max, max, max, max, max, max, 0, max},
      {max, max, max, max, max, max, max, max, max, 0},
    };
    int Arg1 = 3;
    verifyCase(0, new Pair<Integer, Integer>(1, 2), solver.solve(Arr0, Arg1));
  }

  private void testCase1() {
    int max = Integer.MAX_VALUE/10;
    int[][] Arr0 = {
      {0, 80, 60, max, max, max, max, max, max, max},
      {80, 0, 20, max, 90, max, max, max, max, max},
      {60, 20, 0, 50, max, max, max, max, max, max},
      {max, max, 50, 0, 60, max, max, max, max, max},
      {max, 90, max, 60, 0, max, max, max, max, max},
      {max, max, max, max, max, 0, max, max, max, max},
      {max, max, max, max, max, max, 0, max, max, max},
      {max, max, max, max, max, max, max, 0, max, max},
      {max, max, max, max, max, max, max, max, 0, max},
      {max, max, max, max, max, max, max, max, max, 0},
    };
    int Arg1 = 5;
    verifyCase(1, new Pair<Integer, Integer>(2, 240), solver.solve(Arr0, Arg1));
  }

  private void testCase2() {
    int max = Integer.MAX_VALUE/10;
    int[][] Arr0 = {
      {0, 80, 30, max, max, max, max, 50, max, max},
      {80, 0, max, 40, 50, 30, max, max, 40, 20},
      {30, max, 0, 50, 50, 70, 40, 60, 70, 30},
      {max, 40, 50, 0, 60, max, 40, 20, max, 70},
      {max, 50, 50, 60, 0, 50, 30, 50, 60, 50},
      {max, 30, 70, max, 50, 0, max, max, max, max},
      {max, max, 40, 40, 30, max, 0, 90, max, 50},
      {50, max, 60, 20, 50, max, 90, 0, max, 50},
      {max, 40, 70, max, 60, max, max, max, 0, 30},
      {max, 20, 30, 70, 50, max, 50, 50, 30, 0},
    };
    int Arg1 = 10;
    verifyCase(2, new Pair<Integer, Integer>(9, 400), solver.solve(Arr0, Arg1));
  }
}