[Java]백준 1005 ACM Craft

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            int[] D = new int[N + 1];
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                D[j] = Integer.parseInt(st.nextToken());
            }

            // 간선의 수가 많으므로 인접행렬로 구현
            int[][] adjm = new int[N + 1][N + 1];
            int[] indegree = new int[N + 1];
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                
                // 해당 인접행렬 1로 초기화
                adjm[from][to] = 1;
                
                // 선행차수 저장
                indegree[to]++;
            }

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

            solve(N, D, adjm, target, indegree);
        }
    }

    private static void solve(int n, int[] d, int[][] adjm, int target, int[] indegree) {

        // 누적합 작은순 정렬
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        boolean[] visited = new boolean[n + 1];

        // 선행차수가 0인 건물부터 BFS
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) q.offer(new int[]{i, d[i]});
        }

        while (!q.isEmpty()) {

            // 누적합 가장 작은 건물 순으로 확인
            int[] now = q.poll();

            // Target 찾으면 출력 후 종료
            if (now[0] == target) {
                System.out.println(now[1]);
                return;
            }

            visited[now[0]] = true;

            for (int i = 1; i <= n; i++) {

                // 나머지 선행차수 1씩 감소
                if (visited[i] || adjm[now[0]][i] == 0 || --indegree[i] != 0) continue;

                // 누적합 저장
                q.offer(new int[]{i, now[1] + d[i]});
            }
        }
    }
}