특정한 최단 경로

문제풀이

• 다익스트라를 이용하여 풀었다.

• 특정한 두 점을 지나는 최단경로이기 때문에 시작정점으로부터 특정한 두 점까지의 최단거리를 구한다.

• 각 구한 최단거리에서 특정한 두 점 사이의 거리를 구한다.

• 마지막 N 번째 점 까지의 거리를 구한 후 두 가지 경우에 대해서 가장 작은 값이 최단거리이다.

소스코드

const log = console.log;
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

class Heap { /* 구현 내용은 생략 */ }

const [N, E] = input[0].split(" ").map((e) => +e);
const adj = Array.from(Array(N + 1), () => Array(N + 1).fill(Infinity));
input.slice(1, E + 1).map((e) => {
  const [start, end, cost] = e.split(" ").map((el) => +el);
  adj[start][end] = cost;
  adj[end][start] = cost;
});
const [v1, v2] = input[input.length - 1].split(" ").map((e) => +e);

const getMinCost = (start, end) => {
  const queue = new Heap();
  const visited = Array(N + 1).fill(false);
  queue.add([start, 0]);
  while (queue.size()) {
    const [start, cost] = queue.pop();
    if (start === end) return cost;
    visited[start] = true;
    for (let i = 1; i < adj[start].length; i++) {
      const [v, c] = [i, adj[start][i]];
      if (!visited[v] && adj[start][i] !== Infinity) queue.add([v, cost + c]);
    }
  }
  return Infinity;
};

const cost1 = getMinCost(1, v1) + getMinCost(v1, v2) + getMinCost(v2, N);
const cost2 = getMinCost(1, v2) + getMinCost(v2, v1) + getMinCost(v1, N);

if (Math.min(cost1, cost2) === Infinity) {
  log(-1);
  return;
}
log(Math.min(cost1, cost2));