Longest Path in a DAG — Solution & Editorial

Back to the Problem

Topological order DP: relax dist[v] = max(dist[u] + w) as each node is finalized. Longest path is NP-hard in general graphs but linear in a DAG.

Complexity: O(N + M)

Watch out: Weights up to 1000 over 10⁵ edges — path weight reaches 10⁸, safe in 64-bit.