1753 최단경로

"use strict";
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

class Heap {
  constructor() {
    this.heap = [];
  }
  get size() {
    return this.heap.length;
  }
}

class MinHeap extends Heap {
  input(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp(currentIndex = this.size - 1) {
    if (currentIndex < 1) return;

    const currentNode = this.heap[currentIndex];
    const parentIndex = Math.floor((currentIndex - 1) / 2);
    const parentNode = this.heap[parentIndex];

    if (parentNode.cost <= currentNode.cost) return;

    [this.heap[currentIndex], this.heap[parentIndex]] = [
      parentNode,
      currentNode,
    ];
    this.bubbleUp(parentIndex);
  }

  pull() {
    const min = this.heap[0];
    if (this.size === 1) {
      return this.heap.pop();
    }
    this.heap[0] = this.heap.pop();

    this.bubbleDown();
    return min;
  }

  bubbleDown(currentIndex = 0) {
    const leftIndex = currentIndex * 2 + 1;
    const rightIndex = currentIndex * 2 + 2;
    const length = this.size;
    let parentIndex = currentIndex;

    if (
      leftIndex < length &&
      this.heap[leftIndex].cost < this.heap[parentIndex].cost
    ) {
      parentIndex = leftIndex;
    }
    if (
      rightIndex < length &&
      this.heap[rightIndex].cost < this.heap[parentIndex].cost
    ) {
      parentIndex = rightIndex;
    }
    if (parentIndex !== currentIndex) {
      [this.heap[parentIndex], this.heap[currentIndex]] = [
        this.heap[currentIndex],
        this.heap[parentIndex],
      ];
      this.bubbleDown(parentIndex);
    }
  }
}

let N, M, start, graph;

rl.on("line", function (line) {
  if (M === undefined) {
    [N, M] = line.split(" ").map((v) => parseInt(v));
    graph = Array.from(Array(N + 1), () => []);
    return;
  }
  if (start === undefined) {
    start = parseInt(line);
    return;
  }

  M--;
  const [from, to, cost] = line.split(" ").map((v) => parseInt(v));
  graph[from].push([to, cost]);

  if (M === 0) rl.close();
}).on("close", function () {
  const distance = Array.from({ length: N + 1 }, () => "INF");
  const privateQ = new MinHeap();
  privateQ.input({ node: start, cost: 0 });

  distance[start] = 0;

  while (privateQ.size > 0) {
    const { node: now, cost: nowCost } = privateQ.pull();

    if (nowCost > distance[now]) continue;

    for (const [next, nextCost] of graph[now]) {
      if (distance[next] <= nowCost + nextCost) continue;
      distance[next] = nowCost + nextCost;
      privateQ.input({ node: next, cost: distance[next] });
    }
  }

  distance.shift();
  const answer = distance.join("\n");

  console.log(answer);
});