BOJ - 1005 - ACM Craft

import sys
from collections import deque

def solution():
    T = int(input())
    for _ in range(T):
        N, K = map(int, sys.stdin.readline().split())
        time = [0] + list(map(int, sys.stdin.readline().split()))
        graph = [[] for _ in range(N + 1)]
        degree = [0] * (N + 1)
        dp = [0 for _ in range(N+1)]
        dq = deque()
        for _ in range(K):
            X, Y = map(int, sys.stdin.readline().split())
            graph[X].append(Y)
            degree[Y] += 1


        for i in range(1, N + 1):
            if degree[i] == 0:
                dq.append(i)
                dp[i] = time[i]

        while dq:
            index = dq.popleft()
            for j in graph[index]:
                degree[j] -= 1
                dp[j] = max(dp[index] + time[j], dp[j])
                if degree[j] == 0:
                    dq.append(j)

        idx = int(sys.stdin.readline())
        print(dp[idx])
solution()

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