Traders at n posts 0 .. n-1 offer one-way deals: deals[i] = [u, v, fee] moves goods from post u to
post v for a net fee of fee, which may be negative (a profit) or zero. A trader who can find a
loop of deals with a negative total fee can repeat it forever and earn without limit.
Return True if the deal network contains at least one such loop anywhere, otherwise False.
Examples
Input: n = 3, deals = [[0,1,2],[1,2,-3],[2,0,0]]
Output: True
Explanation: 0 -> 1 -> 2 -> 0 has total fee 2 - 3 + 0 = -1.
Input: n = 3, deals = [[0,1,2],[1,2,-3],[2,0,1]]
Output: False
Explanation: the loop totals exactly 0, which is not a profit.
Input: n = 2, deals = [[1,1,-1]]
Output: True
Constraints
1 <= n <= 200,0 <= len(deals) <= 2000,-10**6 <= fee <= 10**6- Target
O(V * E)time.
Goals
- Run Bellman-Ford from a virtual source that reaches every node
- Detect a negative cycle by a successful n-th relaxation round
- Exit early when a round makes no change