787. Cheapest Flights Within K Stops

[LLancelot]

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

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:

代码

• c++

class Solution
{
public:
    
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K)
    {        
        vector<vector<int>> dp(K+2, vector<int>(n, INT_MAX));
        
        //dp[i][j] = Dist to reach j using atmost i edges from src
        
        for(int i = 0; i <= K+1; i++)
        {
            dp[i][src] = 0; // Dist to reach src always zero
        }
        
        for(int i = 1; i <= K+1; i++)
        {
            for(auto &f: flights)
            {
                //Using indegree
                int u = f[0];
                int v = f[1];
                int w = f[2];
                
                if(dp[i-1][u] != INT_MAX)
                    dp[i][v] = min(dp[i][v], dp[i-1][u] + w);
            }
        }
        
        return (dp[K+1][dst] == INT_MAX)? -1: dp[K+1][dst];
    }
};

• Python

        dp = [[float('inf') for _ in range(n)] for _ in range(K+2)]
        for i in range(K+2):
            dp[i][src] = 0
        
        for i in range(1, K+2):
            for f in flights:
                u, v, w = f[0], f[1], f[2]
                # print(u, v, w)
                if dp[i-1][u] != float('inf'):
                    dp[i][v] = min(dp[i][v], dp[i-1][u]+w)
        
        return dp[K+1][dst] if dp[K+1][dst] != float('inf') else -1

[LLancelot]

from heapq import *
class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, total_stops):

        dic = defaultdict(list)
        for start, end, price in flights:
            dic[start].append((end, price))
            
        stop = 0
        heap = [(0, -1, src)]
        while heap:
            cur_price, cur_stop, cur_city = heappop(heap)
            if cur_city == dst:
                return cur_price
            
            if cur_stop < total_stops:
                for nb, nb_price in dic[cur_city]:
                    heappush(heap, (cur_price + nb_price, cur_stop + 1, nb))
        return -1