-
Notifications
You must be signed in to change notification settings - Fork 0
/
10-9.js
45 lines (36 loc) · 903 Bytes
/
10-9.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
const solution = (n, graph) => {
const indegree = Array(n + 1).fill(0);
const list = Array.from(Array(n + 1), () => Array());
const time = Array(n + 1).fill(0);
for (let i = 1; i < n + 1; i++) {
const [cost, ...data] = graph[i - 1];
time[i] += cost;
for (let node of data) {
if (node === -1) continue;
indegree[i] += 1;
list[node].push(i);
}
}
const queue = [];
const result = time.slice();
for (let j = 1; j < n + 1; j++) {
if (indegree[j] === 0) queue.push(j);
}
while (queue.length) {
const now = queue.shift();
for (let k of list[now]) {
result[k] = Math.max(result[k], time[k] + result[now]);
indegree[k] -= 1;
if (indegree[k] === 0) queue.push(k);
}
}
console.log(result.slice(1));
};
const graph = [
[10, -1],
[10, 1, -1],
[4, 1, -1],
[4, 3, 1, -1],
[3, 3, -1],
];
solution(5, graph);