-
Notifications
You must be signed in to change notification settings - Fork 1
/
Dijkstra Shortest Reach 2.js
88 lines (77 loc) · 2.44 KB
/
Dijkstra Shortest Reach 2.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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
function updateNeighbourWeight(edges, index0, index1, weight) {
var newWeight = edges[index0].neighbourDists[index1];
if (newWeight == undefined) {
newWeight = weight;
}
else {
newWeight = Math.min(newWeight, weight);
}
edges[index0].neighbourDists[index1] = newWeight;
edges[index1].neighbourDists[index0] = newWeight;
}
function processTestCase(nodes, S) {
nodes[S].dist = 0;
var stack = [S];
var nextStack = [];
while (stack.length > 0) {
stack.forEach(function (nodeIndex) {
var node = nodes[nodeIndex];
Object.keys(node.neighbourDists).forEach(function (neighbourIndex) {
var neighbourNode = nodes[neighbourIndex];
var newDist = node.dist + node.neighbourDists[neighbourIndex];
if (neighbourNode.dist < 0 || newDist < neighbourNode.dist) {
neighbourNode.dist = newDist;
nextStack.push(neighbourIndex);
}
});
});
stack = nextStack;
nextStack = [];
}
var result = "";
for (var i=0; i<nodes.length; ++i) {
if (i == S) {
continue;
}
result += nodes[i].dist + " ";
}
console.log(result);
}
function processData(input) {
var lines = input.split("\n");
var T = parseInt(lines[0]);
var lineIndex = 1;
for (var i=0; i<T; ++i) {
var lineNM = lines[lineIndex++].split(" ");
var N = parseInt(lineNM[0]);
var M = parseInt(lineNM[1]);
var nodes = [];
for (var j=0; j<N; ++j) {
nodes.push({
index: j,
dist: -1,
neighbourDists: {}
});
}
for (var j=0; j<M; ++j) {
var lineEdge = lines[lineIndex++].split(" ");
var edge0 = parseInt(lineEdge[0]) - 1;
var edge1 = parseInt(lineEdge[1]) - 1;
var weight = parseInt(lineEdge[2]);
updateNeighbourWeight(nodes, edge0, edge1, weight);
updateNeighbourWeight(nodes, edge1, edge0, weight);
}
var S = parseInt(lines[lineIndex++]) - 1;
// console.log(nodes);
processTestCase(nodes, S);
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});