Problem Statement

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return **-1.

Example 1:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown.
The cheapest price from city0 to city2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown.
The cheapest price from city0 to city2 with at most 0 stop costs 500, as marked blue in the picture.

Problem Link

Cheapest Flights Within K Stops - LeetCode

Code

Using BFS and Priority Queue (Gave TLE on Leetcode)

class Solution {
public:
    #define pp pair<int,int>
    #define ppp pair<int,pair<int,int>>
    
    
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        
        vector<vector<pp>> adj(n);
        
        for(auto flight:flights)
        {
            int u = flight[0];
            int v = flight[1];
            int wt = flight[2];
            
            adj[u].push_back({v,wt});
        }
        
        priority_queue<ppp,vector<ppp>,greater<ppp>> pq;
        pq.push({0,{src,k+1}});
        int minEdges = k+1;
        
        while(!pq.empty())
        {
            auto p = pq.top();
            int u = p.second.first;
            int e = p.second.second;
            int wt = p.first;
            pq.pop();
            
            
            
            if(u==dst)
                return wt;
            
            if(e==0)
                continue;
            
            for(auto to:adj[u])
            {
                int v = to.first;
                int w = to.second;
/*The key difference with the classic Dijkstra algo is, we don't maintain the global 
optimal distance to each node, i.e. ignore below optimization:
alt ← dist[u] + length(u, v)
if alt < dist[v]:
Because there could be routes which their length is shorter but pass more stops, 
and those routes don't necessarily constitute the best route in the end. 
To deal with this, rather than maintain the optimal routes with 0..K stops for each node, 
the solution simply put all possible routes into the priority queue, so that all of them 
has a chance to be processed.*/
                **pq.push({wt+w,{v,e-1}});**
                
            }
           
            
            
        }
        return -1;
    }
};
/*To Better understand the solution solve the below test case
5
[[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]]
0
2
2
*/

Using DFS (Gave TLE on Leetcode)

https://www.youtube.com/watch?v=60RbWlDFsmI&list=PLEJXowNB4kPzByLnnFYNSCoqtFz0VKLk5&index=10

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        
        vector<bool> visited(n+1,false);
        vector<vector<int>> adj(n),cost(n+1,vector<int>(n+1));
        
        for(int i=0;i<flights.size();i++)
        {
            adj[flights[i][0]].push_back(flights[i][1]);
            
            
            cost[flights[i][0]][flights[i][1]] = flights[i][2];
        }
        
       
                int fare = INT_MAX;
                dfs(n,adj,src,dst,k,visited,cost,fare,0);
                 
        if(fare==INT_MAX)
            return -1;
        
        return fare;
                
        // }
        
    }
    
    void dfs(int n,vector<vector<int>>& adj,int src,int dst,int k,vector<bool> &visited,vector<vector<int>> cost,int &fare,int totalCost)
    {
        if(k<-1)
            return;
        
        if(src==dst)
        {
            
            fare = min(fare,totalCost);
                 return;
        
        }
        visited[src] = true;
        
        for(int v:adj[src])
        {
            if(!visited[v] and cost[src][v]+totalCost<=fare)
                dfs(n,adj,v,dst,k-1,visited,cost,fare,cost[src][v]+totalCost);
        }
        
        visited[src] = false;
    }
};

Using Dynamic Programming (Leetcode Accepted)

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;i++)
            dp[i][src] = 0;  // Dist to reach src always zero
        
        for(int i=1;i<=k+1;i++)
        {
            for(auto f:flights)
            {
                int u = f[0];
                int v = f[1];
                int wt = f[2];
                
                
                
                
                if(dp[i-1][u]!=INT_MAX and dp[i][v]>dp[i-1][u]+wt)
                    dp[i][v] = dp[i-1][u] + wt;
            }
        }
        
        return dp[k+1][dst]==INT_MAX ? -1 : dp[k+1][dst];
    }
};