787.md

787. Cheapest Flights Within K Stops

Solution 1 (time O(mk), space O(nk))

# Dynamic Programming
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
        """
        dp = [[float("inf") for _ in range(n)] for _ in range(k + 2)]
        dp[0][src] = 0
        for i in range(1, k + 2):
            for cur_s, cur_e, cur_p in flights:
                dp[i][cur_e] = min(dp[i][cur_e], dp[i - 1][cur_s] + cur_p)
        ans = min([dp[i][dst] for i in range(k + 2)])
        return -1 if ans == float("inf") else ans