forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0787-cheapest-flights-within-k-stops.js
64 lines (48 loc) · 1.59 KB
/
0787-cheapest-flights-within-k-stops.js
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
* @param {number} n
* @param {number[][]} flights
* @param {number} src
* @param {number} dst
* @param {number} k
* @return {number}
*/
var findCheapestPrice = function (n, flights, src, dst, K) {
const { graph, seen, minHeap } = buildGraph(n, flights, src, dst, K);
return search(graph, src, dst, seen, minHeap);
};
var initGraph = (n) => ({
graph: new Array(n).fill().map(() => []),
seen: new Map(),
minHeap: new MinPriorityQueue(),
})
var buildGraph = (n, flights, src, dst, K) => {
const { graph, seen, minHeap } = initGraph(n);
for (const [ src, dst, cost ] of flights) {
graph[src].push([ dst, cost ]);
}
const priority = 0;
const node = [ priority, src, (K + 1) ];
minHeap.enqueue(node, priority);
return { graph, seen, minHeap };
}
const search = (graph, src, dst, seen, minHeap) => {
while (!minHeap.isEmpty()) {
const [ cost, city, stops ] = minHeap.dequeue().element;
seen.set(city, stops);
const isTarget = (city === dst);
if (isTarget) return cost;
const canSkip = (stops <= 0);
if (canSkip) continue;
checkNeighbors(graph, cost, city, stops, seen, minHeap);
}
return -1;
}
var checkNeighbors = (graph, cost, city, stops, seen, minHeap) => {
for (let [ nextCity, nextCost ] of graph[city]) {
const hasSeen = (seen.has(nextCity) && ((stops - 1) <= seen.get(nextCity)));
if (hasSeen) continue;
const priority = (cost + nextCost)
const node = [ priority, nextCity, (stops - 1)];
minHeap.enqueue(node, priority);
}
}