forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0787-cheapest-flights-within-k-stops.java
48 lines (39 loc) · 1.21 KB
/
0787-cheapest-flights-within-k-stops.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Time Complexity O(k * n) | Space Complexity O(n)
class Solution {
public int findCheapestPrice(
int n,
int[][] flights,
int src,
int dst,
int k
) {
// initialize an array with max value of size n
int[] prices = new int[n];
Arrays.fill(prices, Integer.MAX_VALUE);
// price from source to source is always 0
prices[src] = 0;
for (int i = 0; i <= k; i++) {
// make a copy of prices
int[] temp = new int[n];
temp = Arrays.copyOf(prices, prices.length);
// loop through flights
for (int j = 0; j < flights.length; j++) {
int s = flights[j][0]; // from
int d = flights[j][1]; // to
int p = flights[j][2]; // price
if (prices[s] == Integer.MAX_VALUE) {
continue;
}
if (prices[s] + p < temp[d]) {
temp[d] = prices[s] + p;
}
}
// set prices to temp
prices = temp;
}
if (prices[dst] != Integer.MAX_VALUE) {
return prices[dst];
}
return -1;
}
}