資訊專欄INFORMATION COLUMN
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.
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];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72675.html
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 ...
摘要：來自大神的解答，只能膜拜。題目確定了至少有一條的行程不存在分支情況，一定有相同的最終目的地，而且對于多條的行程，要選取字母順序較小的一條。 Problem Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the i...
摘要：當(dāng)我們尋找到的第一個非空字符為正或者負(fù)號時，則將該符號與之后面盡可能多的連續(xù)數(shù)字組合起來，作為該整數(shù)的正負(fù)號假如第一個非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來，形成整數(shù)。數(shù)字前正負(fù)號要保留。 Time：2019/4/19Title: String To IntegerDifficulty: MediumAuthor: 小鹿 題目：String To Integer（字...
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 ...
摘要：題目要求用個硬幣搭臺階，要求第級臺階必須有個硬幣。思路和代碼反過來講，如果要搭級臺階，那么級臺階共包含個硬幣。因此我們只需要找到可以搭建的臺階的邊界，并采用二分法將邊界不斷縮小直到達(dá)到最大的臺階數(shù)。 題目要求 You have a total of n coins that you want to form in a staircase shape, where every k-th ...
閱讀 2823·2023-04-25 15:01
閱讀 3088·2021-11-23 10:07
閱讀 3371·2021-10-12 10:12
閱讀 3461·2021-08-30 09:45
閱讀 2200·2021-08-20 09:36
閱讀 3590·2019-08-30 12:59
閱讀 2439·2019-08-26 13:52
閱讀 937·2019-08-26 13:24
