TopCoder SRM 630 Div1 Easy: Egalitarianism3 （グラフ）

解法

ワーシャルフロイトで2点間の最短距離を出しておく。2点を選び、その2点を含む集合を求め、その最大値を返せば良い。

コード

import java.util.ArrayList;

public class Egalitarianism3 {

	public int maxCities(int n, int[] a, int[] b, int[] len) {
		if (n <= 2) {
			return n;
		}
		final int INF = 500000;

		int[][] map = new int[n][n];
		for (int i = 0; i < len.length; i++) {
			int x = a[i] - 1;
			int y = b[i] - 1;
			int l = len[i];

			map[x][y] = l;
			map[y][x] = l;
		}
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map.length; j++) {
				if (map[i][j] == 0) {
					map[i][j] = INF;
				}
			}
		}
		for (int k = 0; k < map.length; k++) {
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
				}
			}
		}

		int max = 0;
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < map.length; i++) {
			for (int j = i + 1; j < map.length; j++) {
				list.clear();
				int d = map[i][j];
				list.add(i);
				list.add(j);
				for (int k = j + 1; k < map.length; k++) {
					boolean joinable = true;
					for (Integer l : list) {
						if (map[k][l] != d) {
							joinable = false;
							break;
						}
					}
					if (joinable) {
						list.add(k);
					}
				}
				max = Math.max(max, list.size());
			}
		}

		return max;
	}

}