CSES 1673 High Score - Algorithm

$1.$ Negate all edge weights to convert the problem.

$2.$ Run Bellman-Ford from node $1$ for $n-1$ iterations.

$3.$ Check for negative cycles using an $n$-th iteration.

$4.$ If a cycle exists, mark all nodes improved in the $n$-th iteration.

$5.$ Propagate the cycle effect using BFS to find all affected nodes.

$6.$ Check if node $n$ is affected.

If yes, output $-1$. Otherwise, output -dist[n]. The core step is propagating cycle effects to all reachable nodes, not the nodes directly in the cycle.