-
Notifications
You must be signed in to change notification settings - Fork 45
/
_787.java
42 lines (34 loc) · 1009 Bytes
/
_787.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
import java.util.stream.IntStream;
/**
* LeetCode 787 - Cheapest Flights Within K Stops
* <p>
* DP
*/
public class _787 {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
final int inf = Integer.MAX_VALUE / 2;
int[][] g = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = inf;
}
}
for (int[] flight : flights) {
int u = flight[0], v = flight[1], w = flight[2];
g[u][v] = Math.min(g[u][v], w);
}
int[] d = IntStream.range(0, n).map(i -> inf).toArray();
d[src] = 0;
K++;
while (K-- > 0) {
int[] dd = d.clone();
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
dd[v] = Math.min(dd[v], d[u] + g[u][v]);
}
}
d = dd;
}
return d[dst] < inf ? d[dst] : -1;
}
}