\(N\)개의 정점과 \(M\)개의 방향 간선으로 이루어진 방향 비순환 그래프, 즉 DAG가 주어진다.

각 간선에는 이동 시간이 있다.

시작 정점 \(S\)에서 도착 정점 \(T\)까지 이동하려고 한다.
가능한 경로 중 이동 시간의 합이 가장 큰 경로를 최장 경로라고 하자.

다음 두 값을 구하시오.

\(S\)에서 \(T\)까지 가는 최장 경로의 길이
\(S\)에서 \(T\)까지 가는 최장 경로에 포함될 수 있는 간선의 개수

어떤 간선이 여러 최장 경로에 포함되더라도 한 번만 센다.

\(2 \le N \le 200\,000\)
\(1 \le M \le 200\,000\)
\(1 \le a, b, S, T \le N\)
\(1 \le w \le 10^9\)
주어지는 그래프는 DAG이다.
\(S\)에서 \(T\)로 가는 경로가 적어도 하나 존재한다.

첫째 줄에 정점의 개수 \(N\)과 간선의 개수 \(M\)이 주어진다.

둘째 줄부터 \(M\)개의 줄에는 간선 정보 \(a\ b\ w\)가 주어진다.

이는 정점 \(a\)에서 정점 \(b\)로 가는 시간이 \(w\)인 방향 간선이 존재한다는 뜻이다.

마지막 줄에는 시작 정점 \(S\)와 도착 정점 \(T\)가 주어진다.

첫째 줄에 \(S\)에서 \(T\)까지 가는 최장 경로의 길이를 출력한다.

둘째 줄에 최장 경로에 포함될 수 있는 간선의 개수를 출력한다.

anthony0506 작성

출처 anthony0506