787 Cheapest Flights Within K Stops

787. Cheapest Flights Within K Stops

1. Question

There arencities connected by mflights. Each fight starts from city uand arrives at vwith a pricew.

Now given all the cities and fights, together with starting citysrcand the destination dst, your task is to find the cheapest price fromsrctodstwith up tokstops. If there is no such route, output-1.

Example 1:

Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1

Output: 200

Explanation:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0

Output: 500

Explanation:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

2. Implementation

(1) Breadth First Search

思路:

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Map<Integer, List<int[]>> adjList = new HashMap();

        for (int[] flight : flights) {
            int fromCity = flight[0];
            int toCity = flight[1];
            int price = flight[2];
            adjList.putIfAbsent(fromCity, new ArrayList());
            adjList.get(fromCity).add(new int[] {toCity, price});
        }


        PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>(new Comparator<int[]>() {
           @Override
            public int compare(int[] a, int[] b) {
                return a[2] - b[2];
            }
        });
        minHeap.add(new int[] {src, 0, 0});

        while (!minHeap.isEmpty()) {
            int[] curInfo = minHeap.remove();
            int curStop = curInfo[0];
            // 到达当前的stops 我们已经转了多少个stop
            int stops = curInfo[1];
            int curCost = curInfo[2];

            if (curStop == dst) {
                return curCost;
            }

            // 只有到达curStop时，转过的stops小于等于K时，我们才继续搜索
            if (stops <= K && adjList.containsKey(curStop)) {
                for (int[] nextInfo : adjList.get(curStop)) {
                    int nextStop = nextInfo[0];
                    int price = nextInfo[1];
                    minHeap.add(new int[] {nextStop, stops + 1, curCost + price});
                }
            }

        }
        return -1;
    }
}

3. Time & Space Complexity