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.

&nbsp;
Example 1:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.


Example 2:

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 above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.


Example 3:

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 above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 100
	0 &lt;= flights.length &lt;= (n * (n - 1) / 2)
	flights[i].length == 3
	0 &lt;= fromi, toi &lt; n
	fromi != toi
	1 &lt;= pricei &lt;= 104
	There will not be any multiple flights between two cities.
	0 &lt;= src, dst, k &lt; n
	src != dst


class Solution:
	def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
		graph = defaultdict(list)
		for u,v,w in flights: graph[u].append((v,w))

		pq = [(0,src,0)]
		dis = [float('inf')]*n

		while pq:
			c,n,l = heappop(pq)
			if n==dst: return c
			if l > k or l>= dis[n]: continue
			dis[n] = l
			for v,w in graph[n]:
				heappush(pq,(c+w,v,l+1))
		return -1
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
       // Initialize Prices arr with infinity & src 0
        int[] prices = new int[n];
        for(int i = 0; i < n; i++)
            prices[i] = Integer.MAX_VALUE;
        prices[src] = 0;
        
        // Build Adj list {key: src | val: dst+price}
        Map<Integer, List<int[]>> flightsMap = new HashMap<>();
        for(int[] flight : flights){
            int flightSrc = flight[0];
            int flightDst = flight[1];
            int flightPrice = flight[2];
            
            List<int[]> flightsList = flightsMap.getOrDefault(flightSrc, new ArrayList<>());
            flightsList.add(new int[]{flightDst, flightPrice});
            flightsMap.put(flightSrc, flightsList);
        }
        
        // Start Bellman ford Algo
        Queue<Integer> q = new LinkedList<>();
        q.offer(src);
        while(k >= 0 && !q.isEmpty()){
            int[] tempPrices = new int[n];                  // Temporary Prices Arr
            for(int i = 0; i < n; i++)
                tempPrices[i] = prices[i];
            
            int size = q.size();
            for(int i = 0; i < size; i++){
                int curSrc = q.poll();
                int curPrice = prices[curSrc];
                List<int[]> curFlightsList = flightsMap.getOrDefault(curSrc, new ArrayList<>());
                for(int[] flight : curFlightsList){
                    int flightDst = flight[0];
                    int flightPrice = flight[1];
                    int newPrice = curPrice + flightPrice;
                    if(newPrice < tempPrices[flightDst]){
                        tempPrices[flightDst] = newPrice;
                        q.offer(flightDst);
                    }
                }
            }
            for(int i = 0; i < n; i++)                    // Copy Temp Prices to Original Price Arr
                prices[i] = tempPrices[i];
            k--;
        }
        int totalPrice = prices[dst];
        return totalPrice == Integer.MAX_VALUE? -1 : totalPrice;
    }
}
class Solution {
public:
    #define f first
    #define s second
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k){
        priority_queue< array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq;
        unordered_map<int, vector<pair<int,int>>> g;

        for(auto& f : flights){
            g[f[0]].push_back({f[1],f[2]});
        }
        vector<int> dis(n,INT_MAX);
        pq.push({0,src,0});
        while(!pq.empty()){
            int c = pq.top()[0];
            int cur = pq.top()[1];
            int lvl = pq.top()[2];
            pq.pop();
            if(cur==dst) return c;
            if(lvl > k || lvl >= dis[cur]) continue;
            dis[cur] = lvl;
            for(auto& nei : g[cur]){
                pq.push({c+nei.s, nei.f, lvl+1});
            }
        }
        return -1;
    }
};
/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
const MAX_PRICE=Math.pow(10,8);
var findCheapestPrice = function(n, flights, src, dst, k) {
    let prev=[];
    let step=0;
    let curr=[];
    for(let i=0;i<n;i++){
        prev[i]=MAX_PRICE;
    }
    prev[src]=0;
    while(step-1<k){
      curr=[...prev];
        let isAnyChange=false;
        for(let i=0;i<flights.length;i++){
            let [src,dst,p]=flights[i];
            if(prev[src]>=MAX_PRICE)continue;
            let totalCostToReachDst=prev[src]+p;
            curr[dst]=Math.min(curr[dst],totalCostToReachDst);
        }
        step++;
        prev=curr;
        
    }
    return prev[dst]>=MAX_PRICE?-1:prev[dst];
    
};
Cheapest Flights Within K Stops