Cheapest Flights Within K Stops

There are n cities connected by m flights. Each flight starts from the city u and arrives at v with a price w.
Now given all the cities and flights, 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

Approach

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CheapestFlightsWithinKStops {
    public static void main(String[] args) {
        int n = 3;
        int[][] edges = { { 0, 1, 100 }, { 1, 2, 100 }, { 0, 2, 500 } };
        int src = 0, dst = 2, k = 1;
        System.out.println(findCheapestPrice(n, edges, src, dst, k));
    }

    static int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        HashMap<Integer, List<int[]>> ump = new HashMap<Integer, List<int[]>>();
        for (int i = 0; i < flights.length; i++) {
            List<int[]> list;
            if (ump.containsKey(flights[i][0])) {
                list = ump.get(flights[i][0]);
            } else {
                list = new ArrayList<>();
            }
            list.add(new int[] { flights[i][1], flights[i][2] });
            ump.put(flights[i][0], list);
        }

        Queue<int[]> q = new LinkedList<int[]>();
        int res = Integer.MAX_VALUE;
        q.add(new int[] { src, 0 });
        int step = 0;

        // itearate till queue is not empty
        while (!q.isEmpty()) {
            int len = q.size();
            for (int i = 0; i < len; i++) {
                int t[] = ((LinkedList<int[]>) q).pop();
                if (t[0] == dst)
                    res = Math.min(res, t[1]);
                if (ump.get(t[0]) != null) {
                    for (int j = 0; j < ump.get(t[0]).size(); j++) {
                        if (t[1] + ump.get(t[0]).get(j)[1] > res)
                            continue;
                        q.add(new int[] { ump.get(t[0]).get(j)[0], 
                        ump.get(t[0]).get(j)[1] + t[1] });
                    }
                }
            }
            if (step++ > K)
                break;
        }
        if (res == Integer.MAX_VALUE)
            return -1;
        else
            return res;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int findCheapestPrice(int n, vector<vector<int>>& flights, 
   int src, int dst, int K) 
{
     unordered_map<int,vector<pair<int,int>>>ump;
     for(int i=0;i<flights.size();i++)
         ump[flights[i][0]].push_back({flights[i][1],flights[i][2]});
     queue<pair<int,int>> q;
     int res=INT_MAX;
     q.push({src,0});
     int step=0;

     //itearate till queue is not empty
     while(!q.empty())
         {
           int len=q.size();
           for(int i=0;i<len;i++)
             {
              auto t=q.front();
              q.pop();
              if(t.first==dst)
                    res=min(res,t.second);
              for(auto j=0;j<ump[t.first].size();j++)
               {
                 if(t.second+ump[t.first][j].second>res)
                       continue;
                 q.push({ump[t.first][j].first,ump[t.first][j].second+t.second});
                  
               }
             }
            if(step++ >K)
                  break;
         }
        if(res==INT_MAX)
              return -1;
        else
            return res;
}

int main()
{
   int  n = 3;
   vector<vector<int>> edges ={{0,1,100},{1,2,100},{0,2,500}};
   int src = 0, dst = 2, k = 1;
   cout<<findCheapestPrice(n,edges,src,dst,k);
   return 0;
}