Cheapest Flights Within K Stops

shriyanshi24jindal

Mar 30th, 2026

103

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 12.96 KB | None | 0 0

copy raw download clone embed print report

class Pair {
int stop, node, cost;
public Pair(int stop, int node, int cost)
{
this.stop = stop;
this.node = node;
this.cost = cost;
}
}
class iPair{
int first, second;
public iPair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// creating adjancency list
ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
for(int i=0;i<n;i++)
adj.add(new ArrayList<iPair>());
for(int[] edge : flights)
{
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new iPair(v, w));
}
// Distance array to store the updated distances from the source.
int[] distance = new int[n];
Arrays.fill(distance, (int)1e9);
distance[src] = 0;
// Queue <stop, node, cost>
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(0,src,0));
while(!q.isEmpty())
{
Pair pair = q.poll();
int stop = pair.stop;
int node = pair.node;
int cost = pair.cost;
// We stop the process as soon as the limit for the stops reaches.
if(stop>k)
continue;
for(iPair neighbour : adj.get(node))
{
int adjNode = neighbour.first;
int adjWeight = neighbour.second;
// We only update the queue if the new calculated distance
// less than the prev and the stops are also within limits.
if(distance[adjNode] > (cost + adjWeight) && stop <= k)
{
distance[adjNode] = cost + adjWeight;
q.add(new Pair(stop+1, adjNode, distance[adjNode]));
}
}
}
// If the destination node is unreachable return ‘-1’
// else return the calculated dist from src to dst.
if(distance[dst] == Integer.MAX_VALUE)
return -1;
return distance[dst];
}
}

RAW Paste Data Copied

class Pair {
    int stop, node, cost;
    public Pair(int stop, int node, int cost)
    {
        this.stop = stop;
        this.node = node;
        this.cost = cost;
    }
}

class iPair{
    int first, second;
    public iPair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // creating adjancency list
        ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
        for(int i=0;i<n;i++)
            adj.add(new ArrayList<iPair>());
        
        for(int[] edge : flights)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];

adj.get(u).add(new iPair(v, w));
        }

// Distance array to store the updated distances from the source. 
        int[] distance = new int[n];
        Arrays.fill(distance, (int)1e9);
        distance[src] = 0;

// Queue <stop, node, cost>
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0,src,0));

while(!q.isEmpty())
        {
            Pair pair = q.poll();
            int stop = pair.stop;
            int node = pair.node;
            int cost = pair.cost;

// We stop the process as soon as the limit for the stops reaches.
            if(stop>k)
                continue;

for(iPair neighbour : adj.get(node))
            {
                int adjNode = neighbour.first;
                int adjWeight = neighbour.second;

// We only update the queue if the new calculated distance
                // less than the prev and the stops are also within limits.
                if(distance[adjNode] > (cost + adjWeight) && stop <= k)
                {
                    distance[adjNode] = cost + adjWeight;
                    q.add(new Pair(stop+1, adjNode, distance[adjNode]));
                }
            }
        }
        // If the destination node is unreachable return ‘-1’
        // else return the calculated dist from src to dst.
        if(distance[dst] == Integer.MAX_VALUE)
            return -1;
        return distance[dst];
    }
}