Untitled

const top = 0;
const parent = i => ((i + 1) >>> 1) - 1;
const left = i => (i << 1) + 1;
const right = i => (i + 1) << 1;
let g = new Array(100005);
let vis = new Array(100005);
class PriorityQueue {
    constructor(comparator = (a, b) => a[0] < b[0]) {
        this._heap = [];
        this._comparator = comparator;
    }
    size() {
        return this._heap.length;
    }
    isEmpty() {
        return this.size() == 0;
    }
    peek() {
        return this._heap[top];
    }
    push(...values) {
        values.forEach(value => {
            this._heap.push(value);
            this._siftUp();
        });
        return this.size();
    }
    pop() {
        const poppedValue = this.peek();
        const bottom = this.size() - 1;
        if (bottom > top) {
            this._swap(top, bottom);
        }
        this._heap.pop();
        this._siftDown();
        return poppedValue;
    }
    replace(value) {
        const replacedValue = this.peek();
        this._heap[top] = value;
        this._siftDown();
        return replacedValue;
    }
    _greater(i, j) {
        return this._comparator(this._heap[i], this._heap[j]);
    }
    _swap(i, j) {
        [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
    }
    _siftUp() {
        let node = this.size() - 1;
        while (node > top && this._greater(node, parent(node))) {
            this._swap(node, parent(node));
            node = parent(node);
        }
    }
    _siftDown() {
        let node = top;
        while (
            (left(node) < this.size() && this._greater(left(node), node)) ||
            (right(node) < this.size() && this._greater(right(node), node))
        ) {
            let maxChild = (right(node) < this.size() && this._greater(right(node), left(node))) ? right(node) : left(node);
            this._swap(node, maxChild);
            node = maxChild;
        }
    }
}

function clean(n) {
    for (let i = 0; i <= n; ++i) {
        g[i] = [];
        vis[i] = 0;
    }
}

function make_graph(edges) {
    for (let i = 0; i < edges.length; i++) {
        let it = edges[i];
        let x = it[0];
        let y = it[1];
        let w = it[2];
        g[x].push([w, y]);
        g[y].push([w, x]);
    }
}
module.exports = {
    //param A : integer
    //param B : array of array of integers
    //param C : integer
    //return a array of integers
    solve: function (n, edges, source) {
        clean(n);
        make_graph(edges);
        let distance = new Array(n).fill(Infinity);
        let q = new PriorityQueue();
        distance[source] = 0;
        q.push([0, source]);
        while (q.size() > 0) {
            let p = q.pop();
            let x = p[1];
            if (vis[x] == 1)
                continue;
            vis[x] = 1;
            for (let i = 0; i < g[x].length; ++i) {
                let y = g[x][i][1];
                let w = g[x][i][0];
                if (distance[x] + w < distance[y]) {
                    distance[y] = distance[x] + w;
                    q.push([distance[y], y]);
                }
            }
        }
        for (let i = 0; i < n; ++i) {
            if (distance[i] == Infinity)
                distance[i] = -1;
        }
        return distance;
    }
};