[JS] 택배 배송

문제

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

 

풀이

다익스트라다와 BFS 알고리즘을 이용한 문제이며, 필자는 큐를 이용한 풀이를 진행했다.

 

1번부터 시작하며 큐에 시작하는 위치를 저장하고 순회를 시작한다. 순회하며 각 지점에 도달하기 까지의 최소 비용을 측정한다. 최단 거리의 경우 st 지점부터 ed 지점까지 소요되는 비용을 더하며 최소 비용을 구한다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e);

const [n, m] = input.shift().split(' ').map(Number);
const arr = input.map(e => e.split(' ').map(Number));
const road = Array.from({ length: n + 1 }, () => []);
const cost = Array.from({ length: n + 1 }, () => Infinity);
const que = [1];

cost[1] = 0;
arr.forEach(([st, ed, co], i) => {
  road[st].push([ed, co]);
  road[ed].push([st, co])
})

while (que.length > 0) {
  const cur = que.shift();
  for (let i = 0; i < road[cur].length; i++) {
    const [ed, co] = road[cur][i];
    if (ed !== 1 && cost[ed] > cost[cur] + co) {
      cost[ed] = cost[cur] + co;
      que.push(ed);
    }
  }
}

console.log(cost[n]);