DAG의 가장 긴 경로
골드 V의견: 0
사이클이 없는 방향 그래프(DAG)가 주어진다. 경로의 길이는 경로에 포함된 간선 가중치의 합이다.
어느 정점에서 시작하고 끝나도 좋다. 가장 긴 경로의 길이를 구하여라. 경로는 정점 하나만으로 이루어질 수도 있으며, 그 길이는 \(0\)이다.
\(1 \le n \le 200\,000\), \(0 \le m \le 300\,000\), \(1 \le w \le 10^9\). 답은 64비트 정수 범위 안에 들어간다.
첫째 줄에 정점의 개수 \(n\)과 간선의 개수 \(m\)이 주어진다. 다음 \(m\)개의 줄에 간선의 정보 \(u\ v\ w\)가 주어진다 — 정점 \(u\)에서 \(v\)로 가는 가중치 \(w\)의 간선이다. 같은 간선이 두 번 주어지는 경우는 없으며, 그래프에 사이클이 없음이 보장된다.
가장 긴 경로의 길이를 출력한다.
5 5
1 2 2
2 3 3
1 3 10
3 4 1
5 3 4
11
\(1 \to 3 \to 4\) 경로의 길이가 \(10+1=11\)로 가장 길다.
3 0
0
간선이 없으면 어떤 경로도 정점 하나뿐이므로 길이는 \(0\)이다.
골드 II막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
DAG의 가장 긴 경로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
DAG의 가장 긴 경로