PreviousNext
Coding/Dynamic programming

Longest path in DAG

Write codeHard35 min

Your task

You are given a DAG of n nodes (0..n-1) with weighted directed edges [u, v, w], w >= 0, representing task durations along dependencies. Return the length of the longest path (maximum total weight) in the DAG over all start/end choices. If the input contains a cycle (so 'longest path' is unbounded/undefined), return -1. A single node with no edges contributes a longest path of 0.

Examples

dag_longest_path(n: int, edges: list[list[int]]) -> int
Example 1
Inputdag_longest_path(5, [[0, 1, 3], [0, 2, 2], [1, 3, 4], [2, 3, 1], [3, 4, 2]])
Output9