I had been solving High Score problem. After reading some blogs, I was able to conclude:

Claim 1: Consider ALL cycles { C(i) } reachable from source S. In the Bellman Ford Algorithm, FOR EVERY cycle C(i), THERE EXISTS A (vertex) in C(i) whose distance is modified in the (nth iteration of the Algorithm) Claim 2: If the distance if a vertex is modified in the (nth iteration), it must be the part of a negative cycle

Can someone verify if These Claims are correct?

The Solution idea to High Score Multiply all edge weights by (-1), now we need to minimize our score S: Source Vertex D: Destination Vertex C: A negative weight directed cycle IF: * In the (nth) iteration if there does not occur any relaxation for any edge, then there is no negative cycle reachable from (S) hence the answer dist(D) from Bellman Ford is the Correct answer ELSE: * There must exist a negative weight cycle reachable from (S). But this does not imply that the Minimum Score to reach (D) is (-INFINITY) ==> It is possible that if we enter the cycle (C), it is not possible to reach (D) so it we can't keep reducing our score by cycling through the cycle. * So we need to check if there exits a negative weight cycle (C) such that it is possible to reach (C) from (S) and then reach (D) from (C). ** If such a (C) exists, the minimum score to reach (D) from (S) is -INFINITY ** Else, bellman ford Gave us th ecorrect answer after the (nth) (or (n-1)th ) iteration All test cases passed Could solmeone Acknowledge if Claim 1 and Claim 2 are correct? I believe they need to be for the correctness of the above mentioned solution.