CT097

Milo’s Maximum Loot on a DAG

HardL10 · SingularityAcceptance: 0.0%XP: 600

Milo’s directed treasure map has no cycles. Starting at node 1, find the maximum treasure obtainable along a path to node n. Input: n m; n node rewards; m directed edges u v. Output maximum path reward from 1 to n, or IMPOSSIBLE.

Example 1:

Input: 4 4 1 2 3 4 1 2 1 3 2 4 3 4
Output: 8

Example 2:

Input: 1 0 -5
Output: -5

Example 3:

Input: 3 1 2 4 6 1 2
Output: IMPOSSIBLE

Constraints:

1≤n≤200000; m≤300000; rewards may be negative.

Tags:

graphs dag topological-sort dynamic-programming
Loading...
Test Cases:No test cases
No test cases available.