임계경로

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

"""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()