题目描述：

LeetCode 787. Cheapest Flights Within K Stops

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Note:

• The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
• The size of flights will be in range [0, n * (n - 1) / 2].
• The format of each flight will be (src, dst, price).
• The price of each flight will be in the range [1, 10000].
• k is in the range of [0, n - 1].
• There will not be any duplicated flights or self cycles.

题目大意：

给定带权有向图flights表示一组航班的价格，以三元组s, d, p形式给出，表示从s到达d需要花费价格p。

求从src出发到达dst，最多经停K个机场时的最少花费。

解题思路：

动态规划（Dynamic Programming）

状态转移方程：

ans = min(ans, costs[k] + prices[k][dst])

​其中costs[k]表示到达位置k时的最小花费，prices[k][dst]表示从k到达dst的航班价格。

Python代码：

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
        """
        INF = 0x7FFFFFFF
        prices = collections.defaultdict(lambda: collections.defaultdict(int))
        for s, t, p in flights:
            prices[s][t] = p
        ans = prices[src][dst] or INF
        queue = [src]
        costs = {src : 0}
        for x in range(K + 1):
            nset = set()
            for loc in queue:
                ans = min(ans, costs[loc] + (prices[loc][dst] or INF))
                for next in prices[loc]:
                    costs[next] = min(costs.get(next, INF), costs[loc] + (prices[loc][next] or INF))
                    nset.add(next)
            queue = list(nset)
        return ans if ans < INF else -1

 

本文链接：http://bookshadow.com/weblog/2018/02/18/leetcode-cheapest-flights-within-k-stops/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码