from collections import deque
n = int(input())
forward = [[] for _ in range(n+1)]
howmany = [0] * (n+1)
time = [0] * (n+1)
for i in range(1, n+1):
a, b, *c = map(int, input().split())
time[i] = a
for j in range(b):
forward[c[j]].append(i)
howmany[i] += 1
d = [0] * (n+1)
q = deque()
work = []
for i in range(1, len(howmany)):
if howmany[i] == 0:
q.append(i)
d[i] = time[i]
while q:
print(d)
x = q.popleft()
work.append(x)
for j in forward[x]:
howmany[j] -= 1
d[j] = max(d[j], d[x] + time[j])
if howmany[j] == 0:
q.append(j)
print(work)
print(max(d))
위상정렬과 dp
앞에서 선행 작업의 합을 누적해서 더해준다(그 중 가장 큰 것)
처음에 선행작업이 0개인 작업이 항상 1개인줄 알고d = [0] * (n+1) d[1] = time[1]
이렇게 했는데 다시 보니까 반드시 하나 이상 존재한다고 그랬다