Longest Path in a DAG

Tasks 0..n−1 form a directed acyclic graph. Each edge [u, v, w] means task v can start w hours after task u. Find the length of the longest path (the critical path). Process nodes in topological order.

Implement longest_path(n, edges).

Input

n: The number of nodes. edges: Edges as [from, to, weight].

Output

Return the total weight of the longest path (0 if there are no edges).

सीमाएँ

1 ≤ n ≤ 100,000; 0 ≤ edges ≤ 200,000; 1 ≤ weight ≤ 10,000; the graph has no cycles

उदाहरण

इनपुट:
n = 4
edges = [
    [0, 1, 3],
    [0, 2, 2],
    [1, 3, 4],
    [2, 3, 6]
]

अपेक्षित आउटपुट:
expected = 8

इनपुट:
long long n = 4;
std::vector<std::vector<long long>> edges = {
    {0, 1, 3},
    {0, 2, 2},
    {1, 3, 4},
    {2, 3, 6}
};

अपेक्षित आउटपुट:
long long expected = 8;

इनपुट:
long n = 4;
long[][] edges = new long[][] {
    new long[] {0, 1, 3},
    new long[] {0, 2, 2},
    new long[] {1, 3, 4},
    new long[] {2, 3, 6}
};

अपेक्षित आउटपुट:
long expected = 8;

इनपुट:
n = 3
edges = []

अपेक्षित आउटपुट:
expected = 0

इनपुट:
long long n = 3;
std::vector<std::vector<long long>> edges = {};

अपेक्षित आउटपुट:
long long expected = 0;

इनपुट:
long n = 3;
long[][] edges = new long[][] {};

अपेक्षित आउटपुट:
long expected = 0;

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

• Wikipedia: Longest path problem