[백준][다익스트라] 1238 파티 NodeJs 구현

     

목차

https://www.acmicpc.net/problem/1238

 

문제 구현 방향

전형적인 다익스트라 문제이다. 

달라진 점은 모든 출발점에서 해주어야 하고 끝점에서 출발점까지 도착하는 것도 계산해야 된다는 부분이다.

 

 

참고

https://be-senior-developer.tistory.com/229

[백준][다익스트라] 1753 최단 경로 NodeJs 구현

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

class MinHeap {
  constructor() {
    this.heap = [null];
  }

  getMin() {
    return this.heap[1];
  }

  getSize() {
    return this.heap.length - 1;
  }

  isEmpty() {
    return this.heap.length < 2;
  }

  insert(node) {
    let current = this.heap.length;

    while (current > 1) {
      const parent = Math.floor(current / 2);
      if (this.heap[parent][0] > node[0]) {
        this.heap[current] = this.heap[parent];
        current = parent;
      } else break;
    }

    this.heap[current] = node;
  }

  remove() {
    let min = this.heap[1];

    if (this.heap.length > 2) {
      this.heap[1] = this.heap[this.heap.length - 1];
      this.heap.splice(this.heap.length - 1);

      let current = 1;
      let leftChildIndex = current * 2;
      let rightChildIndex = current * 2 + 1;

      while (this.heap[leftChildIndex]) {
        let childIndexToCompare = leftChildIndex;
        if (
          this.heap[rightChildIndex] &&
          this.heap[rightChildIndex][0] < this.heap[childIndexToCompare][0]
        )
          childIndexToCompare = rightChildIndex;

        if (this.heap[current][0] > this.heap[childIndexToCompare][0]) {
          [this.heap[current], this.heap[childIndexToCompare]] = [
            this.heap[childIndexToCompare],
            this.heap[current],
          ];
          current = childIndexToCompare;
        } else break;

        leftChildIndex = current * 2;
        rightChildIndex = current * 2 + 1;
      }
    } else if (this.heap.length === 2) {
      this.heap.splice(1, 1);
    } else {
      return null;
    }

    return min;
  }
}

let idx = 1;

let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];

let [N, M, X] = input[0].split(" ").map(Number);

let adj = Array.from({ length: 10001 }, () => []);
while (idx < input.length) {
  let [from, to, cost] = input[idx].trim().split(" ").map(Number);
  adj[from].push([to, cost]);

  idx++;
}

function dijkstra(start, dist) {
  dist[start] = 0;
  let pq = new MinHeap();
  pq.insert([0, start]);
  while (pq.getSize()) {
    let [d, from] = pq.remove();
    for (let [to, n_dist] of adj[from]) {
      let sum = n_dist + d;
      if (sum < dist[to]) {
        dist[to] = sum;
        pq.insert([sum, to]);
      }
    }
  }
}

let ans = 0;

for (let i = 1; i <= N; i++) {
  let dist = Array(10001).fill(9999999);
  let total = 0;
  dijkstra(i, dist);
  total += dist[X];
  dist = Array(10001).fill(9999999);
  dijkstra(X, dist);
  total += dist[i];
  ans = Math.max(total, ans);
}
console.log(ans);