[백준 1005번] ACM Craft 문제 풀이

< 문제 >

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

 

 

< 코드 >

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
for _ in range(n):
    N, K = map(int, input().split())
    arr = [[] for _ in range(N + 1)]  # 연결된 건물 정보 배열
    cnt_arr = [0] * (N+1)

    time = [0] + list(map(int, input().split()))  # 소요 시간 배열
    for _ in range(K):
        a, b = map(int, input().split())
        arr[a].append(b)
        cnt_arr[b] += 1

    target = int(input())
    dp = [-1] + [0]*N
    q = deque()

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


    while q:
        now = q.popleft()
        for node in arr[now]:
            cnt_arr[node] -= 1
            dp[node] = max(dp[node], dp[now] + time[node])
            if cnt_arr[node] ==0:
                q.append(node)

        if cnt_arr[target]==0:
            print(dp[target])
            break