CSES 1673 High Score - Implementation

Here is the solution:

// Negate weights
edges := [(u, v, -w) for u, v, w in original_edges]

// Bellman-Ford
dist := [inf] * (n + 1)
dist[1] := 0
for round from 1 to n - 1
    for (u, v, w) in edges
        if dist[u] + w < dist[v] then
            dist[v] := dist[u] + w

// Check for positive cycle (negative in original)
for (u, v, w) in edges
    if dist[u] + w < dist[v] then
        print -1 // can get infinite score
        return

print -dist[n]

The core step is propagating the cycle effect to all reachable nodes using BFS after detecting which nodes improved.

This runs in $O(VE)$ time and uses $O(V)$ space.