BOJ. ACM Craft (1005)

Problem: BOJ 1005 — ACM Craft · 한국어 · 日本語

Each rule A B means building A must be completed before building B can start. The rules form a directed acyclic graph. Process buildings in topological order so that every prerequisite has its completion time before its dependent building is handled.

Let finish[v] be the earliest time building v can be completed. Its recurrence is finish[v] = duration[v] + max(finish[p]) over prerequisites p, with the maximum over an empty set defined as 0 for a source building. For each edge u -> v, update finish[v] with finish[u] + duration[v], keeping the maximum over all prerequisites. This maximum matters when a building has multiple prerequisite paths: construction can start only after the slowest required predecessor is finished. Initially set finish[v] = duration[v]; this handles source buildings and a target that is itself a source, whose answer is simply its own duration.

Kahn’s algorithm queues every vertex with indegree zero. When a building is removed from the queue, relax all outgoing edges and decrement their indegrees; a dependent building enters the queue only after all its prerequisites have been processed. The target’s accumulated finish value is then the answer for that test case.

The adjacency lists, indegrees, and queue take O(N + K) time and space per test case, where N is the number of buildings and K is the number of rules. long stores completion times safely.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int testCases = input.nextInt();
        StringBuilder output = new StringBuilder();

        while (testCases-- > 0) {
            int n = input.nextInt();
            int k = input.nextInt();
            long[] duration = new long[n];
            long[] finish = new long[n];
            int[] indegree = new int[n];
            List<Integer>[] graph = new ArrayList[n];

            for (int building = 0; building < n; building++) {
                duration[building] = input.nextInt();
                finish[building] = duration[building];
                graph[building] = new ArrayList<>();
            }

            for (int rule = 0; rule < k; rule++) {
                int prerequisite = input.nextInt() - 1;
                int building = input.nextInt() - 1;
                graph[prerequisite].add(building);
                indegree[building]++;
            }

            int target = input.nextInt() - 1;
            int[] queue = new int[n];
            int front = 0;
            int back = 0;
            for (int building = 0; building < n; building++) {
                if (indegree[building] == 0) {
                    queue[back++] = building;
                }
            }

            while (front < back) {
                int prerequisite = queue[front++];
                for (int building : graph[prerequisite]) {
                    finish[building] = Math.max(
                        finish[building],
                        finish[prerequisite] + duration[building]
                    );
                    if (--indegree[building] == 0) {
                        queue[back++] = building;
                    }
                }
            }

            output.append(finish[target]).append('\n');
        }

        System.out.print(output);
    }

    private static class FastScanner {
        private final BufferedReader reader =
            new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer;

        int nextInt() throws IOException {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return Integer.parseInt(tokenizer.nextToken());
        }
    }
}