Spot a looping discount

Scenario

A ride-hailing app prices trips between n zones, numbered 0 to n - 1. A leg is a one-way ride from one zone to another with a fare. During promotions, a leg can have a negative fare: a credit paid to the rider.

You work on the pricing system. A rider who could ride round a loop of legs and end up with a total below zero could collect credit again and again. Before a promotion starts, the system must check for such a loop.

Your task

Write has_loop_discount(n, legs).

n is the number of zones.
legs[i] = [a, b, fare] is a one-way leg from zone a to zone b. fare can be negative.
Return True when some loop of legs, starting and ending in the same zone, has a total fare below 0. Return False otherwise. A loop that totals exactly 0 does not count.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 3, legs = [[0, 1, 4], [1, 2, -2], [2, 0, -3]]
Output: true

Bellman-Ford starts every zone at 0, then relaxes every leg once per round. A round that lowers nothing proves there is no such loop.

Round	Zone 0	Zone 1	Zone 2	Changed?
start	0	0	0
1	-5	0	-2	yes
2	-6	-1	-3	yes
3	-7	-2	-4	yes

With 3 zones, a loop-free map settles within 2 rounds. A third round that still lowers totals means a loop: 0, 1, 2, 0 totals 4 - 2 - 3 = -1.

Example 2#

text2 lines

Input:  n = 3, legs = [[0, 1, 4], [1, 2, -2], [0, 2, 3]]
Output: false

One leg has a credit, but no leg leads back, so there is no loop at all.

Example 3#

text2 lines

Input:  n = 1, legs = []
Output: false

There are no legs, so there is no loop.

Constraints

1 ≤ n ≤ 1,000
0 ≤ len(legs) ≤ 5,000, and every leg is [a, b, fare] with 0 ≤ a, b < n, a ≠ b and -100 ≤ fare ≤ 100

What does n ≤ 1000 tell you?

Here n is only 1,000 and there are at most 5,000 legs. Bellman-Ford makes up to n rounds over m legs, so about 1,000 × 5,000 = 5 million steps, which is fast. That is why this size is small: Dijkstra cannot be used with negative fares, and the safe method is slower. A map of 100,000 zones would be 500 million steps or more.

Scenario

Your task

Write has_loop_discount(n, legs).

n is the number of zones.
legs[i] = [a, b, fare] is a one-way leg from zone a to zone b. fare can be negative.
Return True when some loop of legs, starting and ending in the same zone, has a total fare below 0. Return False otherwise. A loop that totals exactly 0 does not count.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 3, legs = [[0, 1, 4], [1, 2, -2], [2, 0, -3]]
Output: true

Bellman-Ford starts every zone at 0, then relaxes every leg once per round. A round that lowers nothing proves there is no such loop.

Round	Zone 0	Zone 1	Zone 2	Changed?
start	0	0	0
1	-5	0	-2	yes
2	-6	-1	-3	yes
3	-7	-2	-4	yes

With 3 zones, a loop-free map settles within 2 rounds. A third round that still lowers totals means a loop: 0, 1, 2, 0 totals 4 - 2 - 3 = -1.

Example 2#

text2 lines

Input:  n = 3, legs = [[0, 1, 4], [1, 2, -2], [0, 2, 3]]
Output: false

One leg has a credit, but no leg leads back, so there is no loop at all.

Example 3#

text2 lines

Input:  n = 1, legs = []
Output: false

There are no legs, so there is no loop.

Constraints

1 ≤ n ≤ 1,000
0 ≤ len(legs) ≤ 5,000, and every leg is [a, b, fare] with 0 ≤ a, b < n, a ≠ b and -100 ≤ fare ≤ 100

What does n ≤ 1000 tell you?