🎲 백준 1504번 특정한 최단 경로

백준 1504번

🧸 다음번에 응용문제를 도전해보겠다!

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, E] = input.shift().split(" ").map(Number);
const graph = Array.from(new Array(N + 1), () => []);
for (let e = 0; e < E; e++) {
  const [a, b, c] = input[e].split(" ").map(Number);
  graph[a].push([b, c]);
  graph[b].push([a, c]);
}

const [v1, v2] = input[E].split(" ").map(Number);
const result = new Array(2).fill(Infinity);

const dijkstra = (start) => {
  const distArr = new Array(N + 1).fill(Infinity);
  const queue = [[start, 0]];
  distArr[start] = 0;
  while (queue.length) {
    const [to, dist] = queue.shift();
    for (let j = 0; j < graph[to].length; j++) {
      const [nextTo, nextDist] = graph[to][j];
      if (distArr[nextTo] > dist + nextDist) {
        distArr[nextTo] = dist + nextDist;
        queue.push([nextTo, distArr[nextTo]]);
      }
    }
  }

  return distArr;
};

const arr = dijkstra(1);
result[0] = arr[v1];
result[1] = arr[v2];
const arr2 = dijkstra(v1);
result[0] += arr2[v2];
result[1] += arr2[N];
const arr3 = dijkstra(v2);
result[1] += arr3[v1];
result[0] += arr3[N];

const answer = Math.min(...result);
if (answer === Infinity) console.log(-1);
else console.log(answer);