1706. The Most Valuable Run of Jobs

A DIRECTED graph with n vertices and m arrows has NO directed cycle. Each vertex carries a weight which may be negative. Print the largest total weight of any directed path, where a path of a single vertex counts.

weights 3 4 5 6 7, chain 1->2->3->4->5 -> 25 the whole chain weights 10 -100 -100 10, diamond 1->2,1->3, 2->4, 3->4 -> 10 one vertex alone weights -5 -2 -9, no arrows -> -2 the least bad vertex

The second line is the point of the problem. Every route from 1 to 4 pays -100 on the way, so the best thing to do is stand still on vertex 1 and take nothing else. A solution that insists on walking as far as it can gets -180.

## The three things that have to be said

directed? yes. self-loops? impossible: a self-loop is a cycle and the input is acyclic. parallel arrows? allowed. The second copy of an arrow relaxes the same pair again and changes nothing. disconnected? allowed, and the heaviest chain may sit in a piece that does not contain vertex 1 at all.

## What most people try first

Walk every path and total it. That is correct, it is what the expected answers here were checked against, and the number of paths in a DAG is exponential: on a layered graph of 200000 vertices it is astronomically more than the number of atoms worth counting.

The second instinct is to start at every source and greedily take the heaviest out-neighbour. That is wrong for the usual greedy reason: the heaviest next step may lead into a dead end while a lighter step opens a long valuable run.

## One number per vertex is enough

Let best[v] be the largest total of any path that ENDS at v. A path ending at v either is v alone, or arrives along some arrow u -> v, in which case the part before v is a path ending at u. So

best[v] = w[v] + max(0 taken as "no predecessor used", max over arrows u -> v of best[u])

written more simply as: start best[v] at w[v], and for each arrow u -> v try best[u] + w[v].

The answer is max(best[v]) over all v, because the heaviest path ends somewhere.

## Why a topological order is exactly what makes this work

The recurrence reads best[u] while filling best[v], so every predecessor of v must be final before v is touched. A topological order guarantees precisely that, and an acyclic graph is precisely a graph that has one. Kahn's algorithm produces the order and does the relaxation in the same pass: when a vertex is popped its in-degree has reached 0, which means every arrow into it has already been used to relax it, which means best at that vertex is final.

That is also why the problem is easy here and hard in general. The same question on a graph with a cycle is the longest-path problem, which is NP-hard. The acyclicity is not a convenience; it is the whole reason a linear algorithm exists.

## The trap in the initialisation

best[v] starts at w[v], not at 0 and not at minus infinity.

Starting at 0 makes an all-negative graph answer 0, which is not the weight of any path. The 1 0 test with weight -7 is there for that: the answer is -7.

Starting at minus infinity and only ever taking a predecessor means a vertex with no predecessors never gets a value, so a source is never the answer.

## Overflow

A weight is up to 10^9 in magnitude and a path can use all n vertices, so a total reaches 2 * 10^14. A signed 32 bit integer stops at 2147483647, so the accumulator must be 64 bit. A single weight, and even 2000000000, would still fit; it is the SUM that does not. The declared case with three weights of 10^9 totals 3000000000, which a 32 bit accumulator turns into -1294967296.

## Cost

Time O(n + m): Kahn visits each vertex once and each arrow once. Space O(n + m) for the adjacency list, which the constraints force; an adjacency matrix would be 4 * 10^10 entries at n = 2 * 10^5.

## Related

Problem 399 counts the EDGES on the longest path in a DAG, where every step is worth the same and the answer is always "walk as far as possible". Here a step can be worth less than nothing, which is what makes the stopping decision real.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `-1000000000 ≤ w ≤ 1000000000` - `1 ≤ u, v ≤ n` - the graph has no directed cycle, so no self-loop can occur - the same arrow may be listed more than once - the graph may be disconnected - the answer can reach `2 * 10^14` in magnitude, so it needs 64 bits