LC 0787 [M] Cheapest Flights Within K Stops - ALawliet/algorithms GitHub Wiki
Bellman-Ford solves shortest path with (+)/- weights given k stops
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
prices = [float('inf')] * n
prices[src] = 0
for i in range(k + 1):
tmpPrices = prices.copy()
for s, d, p in flights:
if prices[s] == float('inf'):
continue
# if prices[s] + p < tmpPrices[d]:
tmpPrices[d] = min(tmpPrices[d], prices[s] + p)
prices = tmpPrices
return -1 if prices[dst] == float('inf') else prices[dst]