PreviousNext
Coding/Dynamic programming

Critical path length

Write codeMedium30 min

Your task

Given a DAG on n nodes (0..n-1) and a list of weighted directed edges [u, v, w] with positive integer weights, return the maximum total weight of any directed path (the critical path length). A single node with no edges contributes a path of length 0. The graph is guaranteed acyclic.

Examples

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