SHARE
TWEET

Untitled

a guest Oct 14th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
  3.        
  4.         int[][] g = new int[n][n];
  5.         for(int[] flight : flights){
  6.             int source = flight[0], target = flight[1], cost = flight[2];
  7.             g[source][target] = cost;
  8.         }
  9.        
  10.         PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>(){
  11.            public int compare(int[] o1, int[] o2){
  12.                return Integer.compare(o1[2], o2[2]);
  13.            }
  14.         });
  15.        
  16.         //int array with node, stops, price.
  17.         heap.offer(new int[]{src, K+1, 0});
  18.        
  19.         while(!heap.isEmpty()){
  20.             int[] curr = heap.poll();
  21.             int vert = curr[0], remStops = curr[1], price = curr[2];
  22.            
  23.             if(vert == dst) return price;
  24.            
  25.             if(remStops > 0){
  26.                 for(int i = 0; i<n; i++){
  27.                     if(g[vert][i] > 0){
  28.                         heap.offer(new int[]{i, remStops - 1, price+g[vert][i]});
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.         return -1;
  34.     }
  35. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top