787. Cheapest Flights Within K S

这是一道挺难的medium题，
其实这题完全可以标为hard的
这题求K stop之内的最便宜的机票，所以我们状态要记录两个变量，一个是当前站点，一个是当前步数。
graph上的每个node是city + 步数。
因为要求最低的，所以可以用bfs2来做。
按当前花费排序。
因为用priorityQueue,所以每次从heap里取出来的状态第一次访问时一定是该状态的最低值。
所以直接标为visited,以后再遇到就不用访问了。
这题算步数的时候要注意区分next是destination和不是destination情况。如果next不是dst,则如果花了 K + 1 步还没搞定就不用看了。如果 next是dst，则不用检查。

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        if (src == dst) return 0;
        int[][] graph = new int[n][n];
        buildGraph(flights, graph);
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        
        queue.offer(new int[]{src * 100 + 0, 0});
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            if (!visited.add(cur[0])) continue; // dedup at expansion
            int city = cur[0] / 100, stops = cur[0] % 100, prevCost = cur[1];
            if (city == dst) return prevCost;

            for (int next = 0; next < n; next ++ ) {
                if (graph[city][next] == 0) continue;
                if (visited.contains(next * 100 + (stops + 1))) continue;
                if (next != dst && stops + 1 > K) continue;
                queue.offer(new int[] {next * 100 + stops + 1, prevCost + graph[city][next]});  
            }
        }
        return -1;
    }
    private void buildGraph(int[][] flights, int[][] graph) {
        for (int[] f : flights) {
            int src = f[0], des = f[1], pr = f[2];
            graph[src][des] = pr;
        }
    }
}