====== 임계경로 ======

===== 풀이 =====
  * 임계 경로는 활용되는 분야가 많은 중요한 개념이긴 하지만, 구하는 방법은 그냥 위상정렬된 DAG에서 최장경로를 찾으면 끝이고, 이것은 위상정렬 순서대로 DP를 적용하는 흔한 패턴으로 풀수 있다. 자세한 내용은 [[ps:위상 정렬]] 참고
  * 이 문제에서는 임계경로의 길이 뿐만 아니라, 임계경로에 포함되는 엣지들의 갯수를 구해야 한다. 다른 DP문제에서 사용했던것과 비슷한 DP 역추적 방식을 적용하면 그만이기는 하다. 하지만 아무 임계경로 하나를 구하는 것이 아니라, 모든 임계경로를 다 구해야 하므로 DFS방식으로 역추적을 해야 해서 조금 더 귀찮다.
  * 위상정렬+DP를 하는데에 O(V+E), 그리고 그렇게 얻은 임계경로들의 갯수를 세기 위해 DFS를 돌리는데에 다시 O(V+E). 총 시간복잡도는 O(V+E)이다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1948. 임계경로".

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

Tags: [TopologicalSort]
"""

import graphlib
import sys


def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    ts = graphlib.TopologicalSorter()
    pred_graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v, w = [int(x) for x in sys.stdin.readline().split()]
        ts.add(v - 1, u - 1)
        pred_graph[v - 1].append((u - 1, w))
    start, dest = [int(x) for x in sys.stdin.readline().split()]
    critical_path = [[] for _ in range(n)]
    time = [0] * n
    for u in ts.static_order():
        max_time = 0
        for v, time_vu in pred_graph[u]:
            time_u = time[v] + time_vu
            if time_u == max_time:
                critical_path[u].append(v)
            elif time_u > max_time:
                max_time = time_u
                critical_path[u] = [v]
        time[u] = max_time
    answer = 0
    stack = [dest - 1]
    visited = [False] * n
    while stack:
        u = stack.pop()
        if not visited[u]:
            visited[u] = True
            answer += len(critical_path[u])
            stack.extend(critical_path[u])
    print(time[dest - 1])
    print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_5}}