CSES 1673 High Score - Walkthrough

Graph: $1 \to 2$ (score $3$), $2 \to 3$ (score $4$), $3 \to 2$ (score $5$), $2 \to 4$ (score $1$), $n = 4$. After negating: $1 \to 2$ ($-3$), $2 \to 3$ ($-4$), $3 \to 2$ ($-5$), $2 \to 4$ ($-1$). Run Bellman-Ford: after $3$ iterations, dist[2] = -12, dist[3] = -7, dist[4] = -4.

The $4$-th iteration improves dist[3] (to $-16$) and dist[4] (to $-13$) due to cycle $2 \leftrightarrow 3$. Mark all nodes that improved and all nodes reachable from them.

Check two-way reachability: node $2$ (the cycle) is reachable from node $1$ (direct edge $1 \to 2$). Node $4$ is reachable from node $2$ (direct edge $2 \to 4$). Both checks pass. Output $-1$.