작업

• 위상 정렬 (Topological Sorting)의 대표적인 응용인 임계 경로의 길이를 구하는 문제.
• 원래는 위상 정렬을 수행하면서 길이를 계산하는 것이 일반적인 방법인데, 이 문제에서는 주어지는 데이터는 이미 위상정렬이 되어있는 상태이다. 따라서 위상정렬된 결과에서 임계 경로만 계산하면 된다.
• 계산식은
  • n번 작업이 끝날 때까지 필요한 총 시간 = (n번 작업의 선행 작업들중 가장 늦게 끝나는 시간) + n번 작업의 소요시간

"""Solution code for "BOJ Q2056. 작업".

- Problem link: https://www.acmicpc.net/problem/2056
- Solution link: http://www.teferi.net/ps/problems/boj/2056
"""

import sys


def main():
    N = int(sys.stdin.readline())
    complete_times = [0] * (N + 1)
    for i in range(N):
        t, _, *dependencies = [int(x) for x in sys.stdin.readline().split()]
        complete_times[i + 1] = t
        if dependencies:
            complete_times[i + 1] += max([complete_times[work]
                                          for work in dependencies])
    print(max(complete_times))


if __name__ == '__main__':
    main()