2139-Six Degrees of Cowvin Bacon

問題（外部リンク）

2139 -- Six Degrees of Cowvin Bacon

実装の概要

aとbが共演したことがあれば距離1、aとbは共演してはいないがcはaやbと共演したことがあれば距離2、…というようにab間の距離を定義すれば全点対最短路の問題と考えることができます。
n<=300なのでワーシャルフロイド法を使えば十分時間内に答えることができます。なお、最終的な出力は「合計距離最小の場合の平均値の100倍」なので注意が必要です。

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

		String[] tmpArray = br.readLine().split(" ");

		int n = Integer.parseInt(tmpArray[0]);
		int m = Integer.parseInt(tmpArray[1]);

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

		for(int i = 0; i < dist.length; i++){
			Arrays.fill(dist[i], INF);
		}

		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");

			for(int k = 1; k < tmpArray.length; k++){
				int a = Integer.parseInt(tmpArray[k]) - 1;
				for(int l = 1; l < tmpArray.length ; l++){
					if(k == l){
						continue;
					}

					int b = Integer.parseInt(tmpArray[l]) - 1;

					dist[a][b] = 1;
					dist[b][a] = 1;

				}
			}

		}

		//ここまで入力部

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

		solve(shortestPath);
	}

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

		//合計距離の最小値を保存する
		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){
				minSum = tmpSum;
			}

		}

		System.out.println((int)((double)minSum/(n - 1)*100));
	}

	//ワーシャルフロイド法
	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;
	}

}