Circuits.java

Circuits.java

import java.util.*;

public final class Circuits {
	
	public static int howLong(String[] connects, String[] costs) {
		final int size = connects.length;
		final int[][] m = new int[size][size];

		for (int i=0; i<size; ++i) {
			String c = connects[i];
			// System.out.printf("Line %d: %s\n", i, c);
			if (c.trim().equals("")) continue;
			String[] connect = c.split(" ");
			String[] cost = costs[i].split(" ");
			assert connect.length == cost.length;
			for (int j=0; j<connect.length; ++j) {
				int this_cost = Integer.parseInt(cost[j]);
				int this_idx = Integer.parseInt(connect[j]);
				m[i][this_idx] = this_cost;
			}
		}

		// print(m);

		for (int i=0; i<size; ++i) {
			for (int j=0; j<size; ++j) {
				if (i == j) continue;
				for (int k=0; k<size; ++k) {
					if (k == i || k == j) continue;
					int ik = m[i][k];
					int kj = m[k][j];
					int sum = ik + kj;
					if (ik > 0 && kj > 0) {
						m[i][j] = Math.max(m[i][j], sum);
					}
				}
			}
		}

		// System.out.println();

		int max = 0;
		for (int i=0; i<size; ++i) {
			for (int j=0; j<size; ++j) {
				if (m[i][j] > 0) {
					max = Math.max(max, m[i][j]);
				}
			}
		}

		// print(m);

		return max;
	}

	private static void print(int[][] m) {
		for (int[] arr : m) {
			System.out.println(Arrays.toString(arr));
		}
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int size = Integer.parseInt(s.nextLine());
		System.out.printf("size %d\n", size);
		String[] connects = new String[size];
		String[] costs = new String[size];
		for (int i=0; i<size; ++i) {
			connects[i] = s.nextLine().trim();
		}
		for (int i=0; i<size; ++i) {
			costs[i] = s.nextLine().trim();
		}
		System.out.println(howLong(connects, costs));
	}
}