-
Notifications
You must be signed in to change notification settings - Fork 0
/
1005.py
47 lines (39 loc) · 1.25 KB
/
1005.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
times = [0] + list(map(int, input().split()))
graph = defaultdict(list)
preOrderGraph = defaultdict(list)
state = [0 for _ in range(n+1)]
for _ in range(k):
u, v = map(int, input().split())
graph[u].append(v) # 출발: [도착 노드 들]
preOrderGraph[v].append(u) # 도착: [출발 노드들]
state[v] += 1 # 위상 증가 시켜줌
w = int(input()) # 지어야할 건물
# 위상정렬
q = deque()
cnt = 0
for i in range(1, n+1):
if state[i] == 0:
q.append(i)
sortedQ = deque()
while q:
thisNode = q.popleft()
sortedQ.append(thisNode)
for nextNode in graph[thisNode]:
state[nextNode] -= 1
if state[nextNode] == 0:
q.append(nextNode)
dp = [0 for _ in range(n+1)]
while sortedQ:
thisNode = sortedQ.popleft()
dp[thisNode] = times[thisNode]
maxPreNodeTime = 0
for preNode in preOrderGraph[thisNode]:
maxPreNodeTime = max(dp[preNode], maxPreNodeTime)
dp[thisNode] += maxPreNodeTime
print(dp[w])