테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 작업 ======

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


===== 코드 =====
<dkpr py>
"""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()
</dkpr>