https://www.acmicpc.net/problem/1516
https://github.com/stellaluminary/Baekjoon
1005번과 마찬가지로 위상정렬과 DP가 결합된 문제이다.
https://aigong.tistory.com/457
순서가 존재하는 모든 노드에 대해 순서대로 나열하는 위상 정렬에서 DP를 활용하여 시간을 계산해내는 문제이다.
다만 본 문제는 입력이 특이한데 이점을 유의하면서 코드를 구성해야 한다.
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n+1)]
indegree = [0]*(n+1)
time = [0]
for i in range(1, n+1):
t = list(map(int, input().split()))
time.append(t[0])
for j in t[1:-1]:
graph[j].append(i)
indegree[i] += 1
res = [0] * (n + 1)
q = deque()
for i in range(1,n+1):
if indegree[i] == 0:
q.append(i)
res[i] = time[i]
while q:
now = q.popleft()
for k in graph[now]:
indegree[k] -= 1
res[k] = max(res[now]+time[k], res[k])
if indegree[k] == 0:
q.append(k)
for i in res[1:]:
print(i)