# BOJ - 1005 - ACM Craft

Updated:

```
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

## Leave a comment