dp를 적용하여 구하는 위상정렬 문제였다
q에서 값을 뺄 때, 진입차수-1과 동시에 dp[now](이전 건물까지 걸리는 시간)+d[i](이번 건물을 짓는 시간)와 dp[i] 중 더 큰 값을 dp[i]에 저장해주었다
해당 건물이 지어지기 위해서는 앞에 지어질 건물에 드는 시간들 중 가장 긴 시간에 맞춰주어야 모든 건물을 짓고 해당 건물을 지을 수 있기 때문이다
소스 코드
import sys
from collections import deque
input = sys.stdin.readline
T = int(input())
for _ in range(T):
n, k = map(int, input().split())
d = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
indegree = [0 for _ in range(n+1)]
dp = [0 for _ in range(n+1)]
for _ in range(k):
a, b = map(int, input().split())
graph[a].append(b)
indegree[b] += 1
q = deque()
for i in range(1, n+1):
if indegree[i] == 0:
q.append(i)
dp[i] = d[i]
while q:
now = q.popleft()
for i in graph[now]:
indegree[i] -= 1
dp[i] = max(dp[i], dp[now] + d[i])
if indegree[i] == 0:
q.append(i)
target = int(input())
print(dp[target])