Is There a Bargain Loop That Pays You Forever
Implement hasBargainLoop
A network of trading posts has one-way trades, each with a cost (negative means you earn money). Decide whether the network contains a bargain loop: a cycle of trades that brings you back to the starting post with a negative total cost, so that repeating it earns money forever.
Bellman-Ford's relaxation rounds settle down after n − 1 rounds unless a negative cycle exists, which gives a simple test.
Example 1:
Input: cost = [[100,2,100,100,100],[100,100,-4,100,100],[100,100,100,1,100],[100,1,100,100,3],[100,100,100,100,100]]
Output: true
Example 2:
Input: cost = [[100,3],[-2,100]]
Output: false
Example 3:
Input: cost = [[-1]]
Output: true
+ 16 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 7 trading posts numbered 0 … n-1; cost is an n × n matrix: cost[u][v] = 100 means no one-way trade from u to v, otherwise cost[u][v] (−9 … 9, zero allowed) is what you pay for the trade (negative means you gain money) - ●
A trade from a post to itself is allowed (cost[u][u] may be a real value) - ●
A bargain loop is a cycle of trades (returning to the starting post) whose total cost is negative; the loop may be anywhere in the network, not necessarily connected to a particular start - ●
Return true if the network contains a bargain loop, otherwise false
cost =
[[100,2,100,100,100], [100,100,-4,100,100], [100,100,100,1,100], [100,1,100,100,3], [100,100,100,100,100]]