문제 개요

문제: 운동

분류: 그래프 이론, 최단 경로, 플로이드-워셜

난이도: 골드4

문제 풀이

문제에서 주어지는 마을의 개수가 최대 400개로 삼중 반복문을 돌려도 충분하기 때문에 플로이드 와샬 알고리즘을 사용했다.

모든 마을 사이의 최단 거리를 구하면서 출발지와 도착지가 자기 자신인 경우에만 정답 변수와 비교하여 더 작은 값을 저장한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [VE, ...road] = fs.readFileSync(filePath).toString().trim().split("\n");
const [V, E] = VE.split(" ").map(Number);

const solution = () => {
  let answer = Infinity;
  const dist = Array.from({ length: V + 1 }, () =>
    new Array(V + 1).fill(Infinity)
  );

  road.forEach((roadInfo) => {
    const [from, to, d] = roadInfo.split(" ").map(Number);
    dist[from][to] = d;
  });

  for (let k = 1; k <= V; k++) {
    for (let i = 1; i <= V; i++) {
      for (let j = 1; j <= V; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
          if (i === j) answer = Math.min(answer, dist[i][j]);
        }
      }
    }
  }

  if (answer === Infinity) console.log(-1);
  else console.log(answer);
};

solution();