https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
import sys
from collections import deque
si = sys.stdin.readline
def topology_sort() :
q = deque([])
for i in range(1,n+1) :
if indegrees[i] == 0 :
q.append(i)
dp[i] = times[i]
while q :
cur = q.popleft()
for x in graph[cur] :
indegrees[x] -= 1
dp[x] = max(dp[x], dp[cur] + times[x])
if indegrees[x] == 0 :
q.append(x)
T = int(si())
for _ in range(T) :
n,k = map(int,si().split())
times = [0] + list(map(int, si().split()))
dp = [0] * (n+1)
indegrees = [0] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(k) :
u,v = map(int,si().split())
graph[u].append(v)
indegrees[v] += 1
w = int(si())
topology_sort()
print(dp[w])