Longest Path in a DAG

Difficulty: 1600 5000 ms 128 MB

dp graphs

Print the maximum total edge weight of any directed path in a weighted DAG.

Input: the first line has N and M; each of the next M lines has u v w (the graph is acyclic).

Output: the longest path weight (0 if no edges).

Constraints:

• 2 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 2×10⁵
• 1 ≤ w ≤ 1000

Sample Tests

4 4
1 2 3
2 3 4
1 3 2
3 4 1

8

2 1
1 2 5

5

Read the Editorial