Graph Theory37 sections · 1633 units
Open in Course

Problem - High Score

CSES 1673

You are playing a game with nn rooms and mm tunnels. Each tunnel goes from room aa to room bb and changes your score by xx (which can be negative). You start in room 11 and want to reach room nn. What is the maximum score you can get?

This looks like longest path on a DAG, but the graph might have cycles. If there is a positive cycle reachable from room 11 that can reach room nn, you can loop forever and get infinite score.