"The difference here is that while running the N-th iteration, each edge connecting a->b and led us to updating the distance to b must satisfy: a is a part of the negative cycle OR a is not a part of the negative cycle but due to reversing the direction of the edges then a is a node such that the cycle can be reached from a in our original graph. The same applies to b."

In Hint 6 , you said a and b will be those vertices from where the cycle will be reached, as we have reversed the graph. This looks perfectly fine.

But in Hint 7 , you are saying that "at least one of a and b will be part of negative weight cycle." How can we say this?

Why should we greedy about Ai+Bi, i am not getting it, can somebody please explain in detail?

2 1 1

1 5

3 6

think for this testcase, what should be the answer.