1683. The Heaviest Route Within a Step Budget
A DIRECTED graph of n vertices and m arrows has NO directed cycle, and each
arrow carries a weight which may be NEGATIVE. Print the LARGEST total weight of a
route from vertex 1 to vertex n that uses AT MOST k arrows, or the word
none if there is no such route.
``` 5 vertices 1 -> 2 (1) 2 -> 3 (1) 3 -> 5 (1) 1 -> 4 (1) 4 -> 5 (1)
k = 2 -> 2 only the two-arrow route fits k = 3 -> 3 the three-arrow route becomes legal and is heavier ```
## The four 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, at different weights, and the heavier copy wins for
the same arrow count.
unreachable? yes, in two ways: vertex n may be unreachable at all, or
every route to it may need more than k arrows. Print none for
both. When n is 1 the answer is 0 for every k including 0,
since the route of no arrows uses no arrows.
## What most people try first
Problem 1679's single pass, keeping one best weight per vertex, and checking the arrow count at the end. There is no count left to check: one number per vertex cannot say how many arrows it took, and the heaviest route to a vertex may be exactly the one that is now too long.
The sharper version of the mistake is to keep, per vertex, the best weight AND the arrow count of that best weight. That still loses, because the two objectives are incomparable: a route arriving heavy in five arrows and a route arriving lighter in two arrows are both worth keeping when three arrows remain.
Problem 1643 made the same point for a MINIMUM over a general graph. The lesson transfers; the method does not, because here the graph is acyclic and the arrow count can be a dimension rather than a round counter.
## The arrow count is part of the state
Keep best[v][j], the heaviest route from vertex 1 to v using EXACTLY j
arrows, and fill it in topological order:
best[1][0] = 0, everything else unknown
for u in topological order:
for j in 0 .. k-1:
if best[u][j] is unknown: continue
for each arrow u -> v of weight w:
best[v][j+1] = max(best[v][j+1], best[u][j] + w)
answer = max over j of best[n][j], or none if all unknown
The state space is n * (k + 1), which at the limits is
2000 * 101 = 202000 entries.
## Why exactly-j and then a maximum, rather than at-most-j directly
Carrying "at most j" would also work and needs the extra rule that
best[v][j] inherits from best[v][j-1], which is easy to forget and easy to
apply in the wrong place. Carrying EXACTLY j keeps the recurrence to one line
and pushes the "at most" into a maximum at the end, where it cannot be got
wrong. The two are the same amount of work.
## Why the topological order still carries the whole argument
When u is reached, every arrow into u comes from a vertex earlier in the
order, so every entry best[u][*] is already final. The extra index changes
nothing about that: the order is over VERTICES, and the arrow count only ever
increases along an arrow, so no entry is read before it is written.
Note the difference from problem 1646, where the graph may have cycles and the rounds have to be built strictly one from the previous. Acyclicity means the vertex order alone is enough here, and the layers never need separating.
## Overflow, computed rather than assumed
A route uses at most k = 100 arrows of magnitude up to 10^6, so a total
stays within 10^8 in either direction. The limit of a signed 32 bit integer is
2147483647, so 32 bit arithmetic is sufficient here, unlike in problem 1679
where the route length is bounded by n rather than by k. That is worth
computing rather than assuming: the same weights with a different bound on the
route length give a different answer about the type.
## Cost
O((n + m) * k) time and O(n * k) memory, about 10^6 updates at the limits.
Two rows of n would suffice if the arrows were processed by layer, but the
topological sweep visits vertices rather than layers, so the full table is the
simpler structure here.
Constraints - `1 ≤ n ≤ 2000` - `0 ≤ m ≤ 10000` - `0 ≤ k ≤ 100` - `1 ≤ u, v ≤ n` - `-1000000 ≤ w ≤ 1000000` - The graph has no directed cycle.
Input
The first line contains three integers n, m and k.
Each of the next m lines contains three integers u, v and w: a directed arrow from u to v of weight w.
Output
Print one integer, the largest total weight of a route from vertex 1 to vertex n using at most k arrows, or the word none if there is no such route.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.