문제 풀이

작업의 우선순위가 정해져 있으므로
위상정렬을 사용하면 된다.

특정 건물을 짓는 시간을 최소한으로 하기위해서는
동시에 지어질 수 있는 건물들은 동시에 지어야한다.

예를 들어 2번(건설 시간 1초), 3번(건설 시간 100초)을 동시에 지을수 있다면 동시에 짓고 그 중에서 건설 시간이 가장 긴 100초를 dp 배열에 저장하면 된다.

점화식

dp[next] = Math.max(dp[next], dp[cur] + buildTime[next]); 
/* 현재 next를 건설 하기 전에 지어야하는 건물들 중에 건설시간이 가장 긴
 건물을 더 해주는 과정. */

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        StringBuilder ans = new StringBuilder();
        for (int k = 0; k < T; k++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int[] buildTime = new int[N + 1];
            int[] indegree = new int[N + 1];
            int[] dis = new int[N + 1];
            List<List<Integer>> graph = new ArrayList<>();
            
            for (int i = 0; i <= N; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 1; i <= N; i++) {
                buildTime[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph.get(a).add(b);
                indegree[b]++;
            }

            int W = Integer.parseInt(br.readLine());

            Queue<Integer> queue = new LinkedList<>();


            for (int i = 1; i <= N; i++) {
                if (indegree[i] == 0) {
                    queue.offer(i);
                    dis[i] = buildTime[i];
                }
            }

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int next: graph.get(cur)) {
                    dis[next] = Math.max(dis[next], dis[cur] + buildTime[next]);
                    if(--indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
            ans.append(dis[W]);
            ans.append("\n");
        }
        System.out.println(ans);
    }
}