Node.js) 백준 1504번: 특정한 최단경로

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

1504번: 특정한 최단 경로

이전의 백준 1753번: 최단경로 문제랑 같은 문제입니다. 

 

다른 점이 있다면 중간에 반드시 통과를 해야하는 지점이 2개 존재한다는 겁니다. 

 

그러면 두가지 경우가 있습니다. 

시작점을 S,  중간점1을 X, 중간점2를 Y, 도착점을 E 라고 했을 때 

 

S - X - Y - E 로 가던지 S-Y-X-E로 가던지 둘 중 하나를 선택하면 됩니다. 

 

 

임의의 지점s 에서 시작했을 때 각 지점으로가는 최단경로 비용을 배열을 반환하는 함수를 만들고, 

function route(s) {

  let cost = new Array(E + 1).fill(Infinity);
  cost[s] = 0;

  let heap = new MinHeap();
  heap.insert({ node: s, cost: 0 });

  while (!heap.empty()) {
    let now = heap.extractMin();
    for (let i = 0; i < adj[now.node].length; i++) {
      const [n, c] = adj[now.node][i];
      if (cost[n] > now.cost + c) {
        cost[n] = now.cost + c;
        heap.insert({ node: n, cost: cost[n] })
      }
    }
  }

  return cost
}

 

 

 

그걸 토대로 값을 구하면 됩니다.

 

예를 들어서 planA

S에서 시작했을 때. X로 가는 최단경로 비용 + X에서 시작했을 때. Y로 가는 최단경로 비용 + Y에서 시작했을 때. E로 가는 최단경로 비용을 다 더해주면 S - X - Y - E 경로입니다. 

 

 

const routeS = route(S);
const routeX = route(X);
const routeY = route(Y);

const planA = routeS[X] + routeX[Y] + routeY[E];
const planB = routeS[Y] + routeY[X] + routeX[E];
if (planA == Infinity && planB == Infinity) {
  console.log(-1)
} else {
  console.log(planA > planB ? planB : planA)

 

 

 

전체 코드는 아래와 같습니다. 

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

  empty() {
    if (this.heap.length == 0) {
      return true;
    }
    return false;
  }

  swap(arr, x, y) {
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
    return;
  }


  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let currentIndex = this.heap.length - 1;

    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      if (this.heap[parentIndex].cost <= this.heap[currentIndex].cost) break;
      this.swap(this.heap, parentIndex, currentIndex)
      currentIndex = parentIndex;
    }
  }


  extractMin() {
    if (this.heap.length == 1) {
      return this.heap.pop();
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return min
  }

  sinkDown(index) {
    const leftIndex = 2 * index + 1;
    const rightIndex = 2 * index + 2;
    const length = this.heap.length;
    let smallestIndex = index;

    if (leftIndex < length && this.heap[leftIndex].cost < this.heap[smallestIndex].cost) {
      smallestIndex = leftIndex;
    }
    if (rightIndex < length && this.heap[rightIndex].cost < this.heap[smallestIndex].cost) {
      smallestIndex = rightIndex;
    }
    if (smallestIndex !== index) {
      this.swap(this.heap, index, smallestIndex);
      this.sinkDown(smallestIndex)
    }
  }
}


const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split('\n').map(v => v.split(' ').map(v => +v));
const [E, _] = input.shift();
const [X, Y] = input.pop();
const S = 1;

let adj = Array.from(Array(E + 1), () => [])

input.forEach(x => {
  const [u, v, w] = x;
  adj[u].push([v, w]);
  adj[v].push([u, w]);
})

function route(s) {

  let cost = new Array(E + 1).fill(Infinity);
  cost[s] = 0;

  let heap = new MinHeap();
  heap.insert({ node: s, cost: 0 });

  while (!heap.empty()) {
    let now = heap.extractMin();
    for (let i = 0; i < adj[now.node].length; i++) {
      const [n, c] = adj[now.node][i];
      if (cost[n] > now.cost + c) {
        cost[n] = now.cost + c;
        heap.insert({ node: n, cost: cost[n] })
      }
    }
  }

  return cost
}

const routeS = route(S);
const routeX = route(X);
const routeY = route(Y);

const planA = routeS[X] + routeX[Y] + routeY[E];
const planB = routeS[Y] + routeY[X] + routeX[E];
if (planA == Infinity && planB == Infinity) {
  console.log(-1)
} else {
  console.log(planA > planB ? planB : planA)
}