1205. Longest Path in a DAG

Given a directed acyclic graph with n nodes (0 to n-1) and weighted edges [u, v, w], return the maximum total weight of any directed path in the graph (0 if no edges). The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Integer — the longest path weight.

Examples

Input: {"n":4,"edges":[[0,1,3],[0,2,2],[1,3,4],[2,3,1]]}
Output: 7
Explanation: 0->1->3 weighs 7.

Input: {"n":1,"edges":[]}
Output: 0
Explanation: No edges.

Input: {"n":2,"edges":[[0,1,5]]}
Output: 5
Explanation: Single edge.

Constraints

• 1<=n<=10^4

Asked by