문제
풀이
위상 정렬에 대한 문제이다. 해당 index보다 뒷순위에 해당하는 것들이 담긴 인접 리스트와 뒤에 몇명이 있는지를 나타내는 degree배열을 선언해준다.
예를 들어, 5 4 3 2 1 순위라면 5 -> 4, 3, 2, 1 // 4 -> 3, 2, 1 // 3 -> 2, 1 … 이런식이다.
그 이후, dp배열을 통해서 dp[a] = b : a를 짓기 위해서 최대 시간 b가 걸리는 배열을 위상 정렬동안 진행한다.
최종적으로, 원하는 건물의 dp값이 정답이 된다.
소스 코드
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
import sys
from math import *
import collections as cl
T = int(sys.stdin.readline())
for _ in range(T):
N, K = map(int, sys.stdin.readline().split())
rank = [0]
rank.extend(list(map(int, sys.stdin.readline().split())))
degree = [0 for _ in range(N+1)]
tree = [[] for _ in range(N+1)]
dp = [0 for _ in range(N+1)]
for _ in range(K):
a, b = map(int, sys.stdin.readline().split())
degree[b] += 1
tree[a].append(b)
end = int(sys.stdin.readline())
q = cl.deque()
for i in range(1, N+1):
if(degree[i] == 0):
q.append(i)
dp[i] = rank[i]
while(q):
current = q.popleft()
for i in tree[current]:
degree[i] -= 1
dp[i] = max(dp[current]+rank[i], dp[i])
if(degree[i] == 0):
q.append(i)
print(dp[end])
