#10557 - XYZZY

Solved By:	wesley
Theory Difficulty:	medium
Coding Difficulty:	easy
Algorithms Used:	other graph
Solution Description:	Firstly, change all positive energies into negative, and negative energies into positive. Now the energies are more intuitively like costs. Positive is bad, negative is good. Clearly we're trying to find the shortest path to the end, and we may have negative-weight cycles. Therefore, Bellman-Ford will be the algorithm of choice. Now, just because we have a shortest path with cost < 100, that doesn't mean we can actually use that path. The net cost may be < 100, but there may be a section that takes more than 100 energy to traverse. So we need to modify Bellman-Ford a bit. Every time you relax an edge, if the resulting relaxed distance is >= 100, don't relax it, because we can't actually use it. If you find a negative-weight cycle, don't just output "winnable" right away. Make sure that you can actually reach the cycle from the start, and make sure that you can actually reach the end from the cycle.