[LeetCode] 787. Cheapest Flights Within K Stops

W4n9Hu1 发布于2019-08-16 13:59 / 2286人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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