0189-Convenient Location

問題（外部リンク）

Convenient Location | Aizu Online Judge

実装の概要

ある点から他の点までの最短路を全ての点について行う全点対最短路問題なのでワーシャルフロイド法で解くことができます。かかりますが、町の数が最大でも10なので時間は気にしなくても大丈夫です。
今回の問題におけるおそらく最大の注意点は、町と町の間の距離が0ということも有り得るということです。そのため、入力されたデータを行列で管理する際に「経路が無い」という状態を0以外の数字で表す必要があります。
INFを自分で定義したのは、ワーシャルフロイド法の計算でのオーバーフローを防ぐためです。距離として有り得る数字は小さいので、これはまあまあ大きい値であれば十分です。

public class Main {
	static final int INF = 99999;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			int n = Integer.parseInt(br.readLine());

			if(n == 0){
				break;
			}

			int[][] dist = new int[10][10];
			int numOfTown = 0;
			//今回の問題では距離0も有り得るのでINFで初期化
			for(int i = 0; i < dist.length; i++){
				Arrays.fill(dist[i], INF);
			}

			for(int i = 0; i < n; i++){
				String[] tmpArray = br.readLine().split(" ");

				int a = Integer.parseInt(tmpArray[0]);
				int b = Integer.parseInt(tmpArray[1]);
				int c = Integer.parseInt(tmpArray[2]);

				dist[a][b] = c;
				dist[b][a] = c;

				numOfTown = Math.max(numOfTown, a + 1);
				numOfTown = Math.max(numOfTown, b + 1);


			}

			int[][] shortestPath = allPairsShortestPath(dist, numOfTown);

			solve(shortestPath);
		}
	}

	static void solve(int[][] matrix){
		int n = matrix.length;

		//合計距離最小の起点とその距離を保存する
		int minId = 0;
		int minSum = Integer.MAX_VALUE;

		for(int i = 0; i < n; i++){
			int tmpSum = 0;

			for(int j = 0; j < n; j++){
				tmpSum += matrix[i][j];
			}

			if(minSum > tmpSum){
				minId = i;
				minSum = tmpSum;
			}

		}

		System.out.println(minId+" "+minSum);
	}

	//ワーシャルフロイド法
	static int[][] allPairsShortestPath(int[][] input, int n){

		int dist[][] = new int[n][n];

		for(int u = 0; u < n; u++){
			for(int v = 0; v < n; v++){
				dist[u][v] = INF;
			}
			dist[u][u] = 0;

			for(int v = 0; v < n; v++){
				if(u != v && input[u][v] < INF){
					dist[u][v] = input[u][v];
				}
			}
		}

		for(int k = 0; k < n; k++){
			for(int u = 0; u < n; u++){
				for(int v = 0; v < n; v++){
					dist[u][v] = Math.min(dist[u][v], dist[u][k] + dist[k][v]);
				}
			}
		}

		return dist;
	}

}