글 읽기 - [node.js] 1916번 100%에서 틀리는 이유를 모르겠습니다.

y2kdj9723 1년 전 0

100%까지 올라가서 자꾸 틀렸다고 나옵니다.. 도대체 어느 부분에서 틀린건지 아무리 봐도 모르겠네요..ㅠㅠ

고수님들께 부탁드리겠습니다 ㅠㅠ

// 우선순위 큐 => 최소 힙 구현
class MinHeap {
  constructor() {
    this.nodes = [];
  }

  addNode(node) {
    this.nodes.push(node);
    this.bubbleUp();
  }

  bubbleUp(index = this.nodes.length - 1) {
    if (index == 0) return;

    let parentIndex = Math.floor((index - 1) / 2);
    let parent = this.nodes[parentIndex];

    if (this.nodes[index].c < this.nodes[parentIndex].c) {
      this.nodes[parentIndex] = this.nodes[index];
      this.nodes[index] = parent;
      this.bubbleUp(parentIndex);
    }
  }

  extractMin() {
    if (this.nodes.length == 1) return this.nodes.pop();

    let min = this.nodes[0];
    this.nodes[0] = this.nodes.pop();

    this.sinkDown();

    return min;
  }

  sinkDown(index = 0) {
    let parent = this.nodes[index];
    let leftIndex = 2 * index + 1;
    let rightIndex = 2 * index + 2;

    if (!this.nodes[leftIndex] && !this.nodes[rightIndex]) return;
    if (!this.nodes[rightIndex]) {
      if (this.nodes[leftIndex].c < this.nodes[index].c) {
        this.nodes[index] = this.nodes[leftIndex];
        this.nodes[leftIndex] = parent;
        this.sinkDown(leftIndex);
      }
    } else {
      if (this.nodes[leftIndex].c <= this.nodes[rightIndex].c) {
        if (this.nodes[leftIndex].c < this.nodes[index].c) {
          this.nodes[index] = this.nodes[leftIndex];
          this.nodes[leftIndex] = parent;
          this.sinkDown(leftIndex);
        }
      } else {
        if (this.nodes[rightIndex].c < this.nodes[index].c) {
          this.nodes[index] = this.nodes[rightIndex];
          this.nodes[rightIndex] = parent;
          this.sinkDown(rightIndex);
        }
      }
    }
  }
}

// 여기서부터 로직 수행
const fs = require("fs");
let [n, m, ...arr] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
arr = arr.map((a) => a.trim().split(" ").map(Number));
let dest = arr.pop();
let obj = {};

arr.forEach((a) => {
  if (!obj[a[0]]) obj[a[0]] = {};

  if (!obj[a[0]][a[1]]) {
    obj[a[0]][a[1]] = a[2];
  } else {
    obj[a[0]][a[1]] = Math.min(obj[a[0]][a[1]], a[2]);
  }
});

let distance = new Array(+n + 1).fill(-1);
let minHeap = new MinHeap();

for (let key in obj[dest[0]]) {
  minHeap.addNode({ v: key, c: obj[dest[0]][key] });
}

while (minHeap.nodes.length) {
  let ex = minHeap.extractMin();
  if (distance[ex.v] == -1 || distance[ex.v] > ex.c) {
    distance[ex.v] = ex.c;
  }

  if (obj[ex.v]) {
    for (let key in obj[ex.v]) {
      let nextV = +key;
      let nextCost = obj[ex.v][key];

      if (distance[nextV] == -1) {
        minHeap.addNode({ v: nextV, c: ex.c + nextCost });
      }
    }
  }
}

console.log(distance[dest[1]]);

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[node.js] 1916번 100%에서 틀리는 이유를 모르겠습니다.

y2kdj9723 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말