241012 ACM Craft

private static class FastScanner {
	private BufferedReader br;
	private StringTokenizer st;

	public FastScanner() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public int nextInt() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = br.readLine();
			if (line == null) {
				return -1;
			}
			st = new StringTokenizer(line);
		}
		return Integer.parseInt(st.nextToken());
	}
}

public static void main(String[] args) throws IOException {
	FastScanner sc = new FastScanner();
	StringBuilder sb = new StringBuilder();

	int testCases = sc.nextInt();

	while (testCases-- > 0) {
		int numberOfBuilds = sc.nextInt();
		int numberOfRules = sc.nextInt();

		int[] buildCosts = new int[numberOfBuilds + 1];
		for (int i = 1; i <= numberOfBuilds; i++) {
			buildCosts[i] = sc.nextInt();
		}

		List<List<Integer>> dependencies = new ArrayList<>();
		for (int i = 0; i <= numberOfBuilds; i++) {
			dependencies.add(new ArrayList<>());
		}

		for (int i = 0; i < numberOfRules; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			dependencies.get(to).add(from);
		}

		int targetBuild = sc.nextInt();

		int[] cache = new int[numberOfBuilds + 1];
		Arrays.fill(cache, -1);

		int totalCost = computeMaxCost(targetBuild, dependencies, buildCosts, cache);
		sb.append(totalCost).append('\n');
	}

	System.out.print(sb.toString());
}

private static int computeMaxCost(int build, List<List<Integer>> dependencies, int[] buildCosts, int[] cache) {
	if (cache[build] != -1) {
		return cache[build];
	}

	int maxCost = 0;
	for (int dependency : dependencies.get(build)) {
		int depCost = computeMaxCost(dependency, dependencies, buildCosts, cache);
		if (depCost > maxCost) {
			maxCost = depCost;
		}
	}

	cache[build] = maxCost + buildCosts[build];
	return cache[build];
}

출처:https://www.acmicpc.net/problem/1005