DAG 최장 경로

위상 순서대로만 max 전이를 흘린다

일반 그래프의 최장 경로는 어렵지만, DAG에서는 선행 정점이 먼저 확정되므로 dp[v] = max(dp[v], dp[u] + w)가 안전합니다.

가중치 DAG에서 1에서 4까지 최장 경로는 1-2-4 +3 +2 +4 +1 1 2 3 4
위상 순서 1, 2, 3, 4 또는 1, 3, 2, 4 모두 가능
시작점 1
dp[1] 0
dp[2] 3
dp[3] 2
dp[4] 7
2 → 4: max(-∞, 3 + 4) = 7 먼저 확정된 dp[2]가 dp[4]의 후보가 됩니다.
3 → 4: max(7, 2 + 1) = 7 더 짧은 경로는 기존 최장값을 바꾸지 않습니다.