https://leetcode.com/problems/cheapest-flights-within-k-stops/description/

787.cheapest_flights_within_K_stops.py

# Time: O(E∗K), where E is the length of flights.
# Space: O(n), the space used to store cur and pre
# Reference: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/


# Bellman-ford algorithm
class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        dist = [[float('inf')] * n for _ in xrange(2)] # [pre, cur] or [cur, pre]
        dist[0][src] = dist[1][src] = 0
        
        for i in xrange(K+1):
            for u, v, w in flights:
                dist[i&1][v] = min(dist[i&1][v], dist[~i&1][u] + w)
        
        return dist[K&1][dst] if dist[K&1][dst] < float('inf') else -1