Critical Path Length

Problem

Given a weighted DAG of n tasks, find the length of the critical path: the maximum total weight of any directed path.

edges is a list of [u, v, w] triples with w > 0, meaning v depends on u and takes w time after u. Process nodes in topological order and relax each edge to its latest finish time. Return -1 if the graph has a cycle.

Hint

Earliest finish time of a node is the maximum over its incoming edges.

Test cases

case 1

in: [6,[[0,1,3],[0,2,2],[1,3,2],[2,3,4],[3,4,3],[1,4,1]]]

expected: 9

case 2

in: [1,[]]

expected: 0

case 3

in: [4,[[0,1,1],[1,2,2],[2,3,3]]]

expected: 6

case 4

in: [4,[[0,1,1],[0,2,4],[1,3,1],[2,3,1]]]

expected: 5

Starter codePython

import heapq
def critical_path_length(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor