---
title: 1787. Cheapest Flights Within K Stops
tags: graph
description: share source code.
---

# 787. Cheapest Flights Within K Stops

class Solution {
    
   static class Edge{
        int val;
        int w;
        int k;
        
        public Edge(int val, int w, int k){
            this.val = val;
            this.w = w;
            this.k = k;
        }
    }
    
    
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        
        List<Edge> [] graph = new ArrayList[n + 1];
        Arrays.setAll(graph, v -> new ArrayList<>());
        for(int flight [] : flights){
            graph[flight[0]].add(new Edge(flight[1], flight[2], 0));
        }
        
        PriorityQueue<Edge> q = new PriorityQueue<>( ( a, b) -> a.w - b.w);
        q.offer(new Edge(src, 0, 0));
        
        int dist [] = new int [n + 1];
        
        while(!q.isEmpty()){
            Edge edge = q.poll();
     
            if(edge.val == dst){
                return edge.w;
            }
        
            if(edge.k > k){
                continue;
            }
            for(Edge v : graph[edge.val]){                
                q.offer(new Edge(v.val, dist[v.val], edge.k + 1));
            }
        }
        
        return -1; 
    }
}