Baekjoon 1446번 지름길

문제

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

걸린 시간

-

풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

class Heap {
  constructor (compare = (a, b) => a < b) { // default : 최소 힙
    this.heap = [null];
    this.compare = compare;
  }
  insert(item) {
    this.heap.push(item);
    let i = this.heap.length-1;
    while(i !== 1 && this.compare(item, this.heap[Math.floor(i/2)])){
      this.heap[i] = this.heap[Math.floor(i/2)];
      i = Math.floor(i/2);
    }
    this.heap[i] = item;
  }
  delete() {
    const item = this.heap[1];
    const tmp = this.heap.pop();
    const len = this.heap.length-1;
    let parent = 1;
    let child = 2;
    while(child <= len){
      if(
        child < len &&
        this.compare(this.heap[child+1], this.heap[child])
      ){
        child += 1;
      }
      if(this.compare(tmp, this.heap[child])){
        break;
      }
      this.heap[parent] = this.heap[child];
      parent = child;
      child *= 2;
    }
    if(this.heap.length > 1) this.heap[parent] = tmp;
    return item;
  }
  empty() {
    return this.heap.length === 1;
  }
}

class PriorityQueue {
  constructor (compare) {
    this.heap = new Heap(compare);
  }
  empty() {
    return this.heap.empty();
  }
  push(item) {
    this.heap.insert(item);
  }
  pop() {
    if(!this.empty()) return this.heap.delete();
    else return null;
  }
}

const [n, d] = input().split(' ').map(Number);
const adj = Array.from(Array(10001), () => Array());
const pq = new PriorityQueue((a, b) => a[0] < b[0]);
for(let i = 0; i < n; i++){
  const [u, v, l] = input().split(' ').map(Number);
  adj[u].push([l, v]);
}

for(let i = 0; i < 10000; i++){
  adj[i].push([1, i+1]);
}

pq.push([0, 0]);
const dist = Array(10001).fill(Number.POSITIVE_INFINITY);
dist[0] = 0;
while(!pq.empty()){
  const [cost, here] = pq.pop();
  if(dist[here] < cost) continue;
  for(let i = 0; i < adj[here].length; i++){
    let [nextDist, there] = adj[here][i];
    nextDist += cost;
    if(nextDist < dist[there]){
      dist[there] = nextDist;
      pq.push([nextDist, there]);
    }
  }
}

console.log(dist[d]);

정점마다 1km 씩 앞으로 나아가는 경로를 인접배열에 추가로 저장해주고 다익스트라 알고리즘을 돌려주면 d km 까지 최단거리를 구할 수 있다.