<abbr id="aewgg"></abbr>

[LeetCode] 787. Cheapest Flights Within K Stops

W4n9Hu1 發布于2019-08-16 13:59 / 2291人閱讀

Problem

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. 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 graph looks like this:

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 graph looks like this:

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

The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
The size of flights will be in range [0, n * (n - 1) / 2].
The format of each flight will be (src, dst, price).
The price of each flight will be in the range [1, 10000].
k is in the range of [0, n - 1].
There will not be any duplicated flights or self cycles.

Solution

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[] costs = new int[n];
        Arrays.fill(costs, Integer.MAX_VALUE);
        costs[src] = 0;
        Queue queue = new LinkedList<>();
        queue.offer(src);
        int stops = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int[] flight: flights) {
                    if (flight[0] != cur || stops > K) continue;
                    if (stops == K && flight[1] != dst) continue;
                    int next = flight[1];
                    int price = flight[2];
                    if (costs[next] > costs[cur]+price) {
                        costs[next] = costs[cur]+price;
                        queue.offer(next);
                    }
                }
            }
            stops++;
        }
        return costs[dst] == Integer.MAX_VALUE ? -1 : costs[dst];
    }
}

云服務器 GPU云服務器 Flights Stops Cheapest within

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72675.html

[LeetCode] 568. Maximum Vacation Days

Problem LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in ...

468122151 2019-08-16 13:39 評論0 收藏0
[LeetCode] Reconstruct Itinerary

摘要：來自大神的解答，只能膜拜。題目確定了至少有一條的行程不存在分支情況，一定有相同的最終目的地，而且對于多條的行程，要選取字母順序較小的一條。 Problem Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the i...

jubincn 2019-08-14 14:02 評論0 收藏0
LeetCode 之 JavaScript 解答第8題 —— 字符串轉換整數（String to

摘要：當我們尋找到的第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續數字組合起來，作為該整數的正負號假如第一個非空字符是數字，則直接將其與之后連續的數字字符組合起來，形成整數。數字前正負號要保留。 Time：2019/4/19Title: String To IntegerDifficulty: MediumAuthor: 小鹿題目：String To Integer（字...

zhisheng 2019-08-23 17:03 評論0 收藏0
[LeetCode] Maximum Size Subarray Sum Equals k

Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...

MudOnTire 2019-08-15 15:47 評論0 收藏0
leetcode441. Arranging Coins

摘要：題目要求用個硬幣搭臺階，要求第級臺階必須有個硬幣。思路和代碼反過來講，如果要搭級臺階，那么級臺階共包含個硬幣。因此我們只需要找到可以搭建的臺階的邊界，并采用二分法將邊界不斷縮小直到達到最大的臺階數。題目要求 You have a total of n coins that you want to form in a staircase shape, where every k-th ...

Ali_ 2019-08-16 17:30 評論0 收藏0