leetcode787.K站中转最便宜航班

思路：将出发点加入小顶堆 中，之后每优先处理价格最小的那一段路径，若是终点则返回价格，否则再走一步，并且加入到堆中放到下一批处理；

也就是每一次优先处理价格最小的

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int [][] g = new int[n][n];
        for(int []f : flights){
            g[f[0]][f[1]] = f[2];
        }
        PriorityQueue<int []> heap = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int [] o1, int [] o2){
                return o1[0] - o2[0];
            }
        });
        heap.offer(new int[]{0,src,K+1});
        while(!heap.isEmpty()){
            int [] t = heap.poll();
            int price = t[0];//这样不容易弄混数组中值的含义
            int place = t[1];
            int remainSteps = t[2];
            if(place == dst){
                return price;
            }
            if(remainSteps > 0){
                for(int i = 0; i < n; i++){
                    if(g[place][i] > 0){
                        heap.offer(new int[]{price + g[place][i], i, remainSteps - 1});
                    }
                }
            }
        }
        return -1;
    }
}

2020/09/09