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