Graph Theory37 sections · 1633 units
Open in Course

CSES 1673 High Score - Detecting Positive Cycles

(In the original graph)

After negating weights, a positive cycle in the original graph becomes a negative cycle in the converted graph. A positive cycle is a loop where you gain score by traversing it. Bellman-Ford will detect this negative cycle in the converted graph, which means you can achieve infinite score in the original problem by looping through the cycle.

But you also need to check if the cycle is reachable from room 11 and if room nn is reachable from the cycle. If the cycle is not on any path from 11 to nn, it does not affect the answer.