let input = require("fs").readFileSync("/dev/stdin", "utf8");
const lines = input.trim().split("\n");
let v, e, r, path = []
for (let i = 0; i < lines.length; i++) {
if (i === 0) {
[v, e, r] = lines[i].split(" ").map((v) => parseInt(v));
path = [...Array(v)].map(() => new Set());
continue;
}
const [s, t, d] = lines[i].split(" ").map((v) => parseInt(v));
path[s].add([t, d])
}
const parent = (i) => Math.floor((i - 1) / 2)
const leftChild = (i) => 2 * i + 1
const rightChild = (i) => 2 * i + 2
const MinHeap = function (n) {
this.a = [...Array(n).keys()].map(v => [v, Number.MAX_SAFE_INTEGER]) // [vertex, weight]
this.pos = [...Array(n).keys()].map(v => v)
this.size = n
}
MinHeap.prototype.extractMin = function () {
const [v, w] = this.a[0]
this.swap(0, this.size - 1)
this.size--
this.popDown(0)
return [v, w]
}
MinHeap.prototype.swap = function (i, j) {
const vi = this.a[i][0], vj = this.a[j][0];
[this.a[i], this.a[j]] = [this.a[j], this.a[i]];
[this.pos[vi], this.pos[vj]] = [this.pos[vj], this.pos[vi]]
}
MinHeap.prototype.decreaseKey = function (v, val) {
const i = this.pos[v]
this.a[i][1] = val
this.popUp(i)
}
// vertexが含まれているか
MinHeap.prototype.contains = function (v) {
return this.pos[v] < this.size
}
// 適切な位置まで上げる
MinHeap.prototype.popUp = function (i) {
let pi = parent(i)
while (i > 0 && this.a[i][1] < this.a[pi][1]) { // 親が子より大きかったら交換
this.swap(i, pi)
i = pi
pi = parent(i)
}
}
// 値を取得
MinHeap.prototype.val = function (v) {
return this.a[this.pos[v]][1]
}
// 適切な位置まで下げる
MinHeap.prototype.popDown = function (i) {
const val = this.a[i][1]
let candidate = null // 子供のほうが小さかったら交換
const ri = rightChild(i)
const li = leftChild(i)
if (ri < this.size) { // right child exist
if (this.a[ri][1] < val) {
candidate = ri
}
}
if (li < this.size) {
if (candidate == null) {
if (this.a[li][1] < val) {
candidate = li
}
} else {
if (this.a[li][1] < this.a[ri][1]) {
candidate = li
}
}
}
if (candidate != null) {
this.swap(i, candidate)
this.popDown(candidate)
}
}
function dijkstra(n, r, path) {
const minHeap = new MinHeap(n)
const dist = Array(n).fill(null)
const parent = Array(n).fill(null)
// initialization
minHeap.decreaseKey(r, 0)
dist[r] = 0
while (minHeap.size > 0) {
const [u, d] = minHeap.extractMin()
for (const [v, w] of path[u]) {
if (!minHeap.contains(v)) {
continue
}
if (d + w < minHeap.val(v)) {
parent[v] = u
dist[v] = d + w
minHeap.decreaseKey(v, d + w)
}
}
}
for (const d of dist) {
if (d == null) {
console.log('INF')
} else {
console.log(d)
}
}
}
// console.log(v, e, r)
// console.log(path)
dijkstra(v, r, path)
Top comments (0)