🎲 백준 21940번 가운데에서 만나기

백준 21940번

🧸 다음은 응용문제 도전!!

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M] = input.shift().split(" ").map(Number);
const arr = Array.from(new Array(N + 1), () => new Array(N + 1).fill(Infinity));
for (let m = 0; m < M; m++) {
  const [a, b, v] = input[m].split(" ").map(Number);
  arr[a][b] = v;
}
const K = +input[M];
const house = input[M + 1].split(" ").map(Number);

for (let g = 1; g < N + 1; g++) {
  for (let i = 1; i < N + 1; i++) {
    for (let j = 1; j < N + 1; j++) {
        if (i === j) {
        arr[i][j] = 0;
        continue;
      }
      if (arr[i][g] + arr[g][j] < arr[i][j]) {
        arr[i][j] = arr[i][g] + arr[g][j];
      }
    }
  }
}

let min = Infinity;
let answer = [];
for (let n = 1; n < N + 1; n++) {
  let max = 0;
  for (let h = 0; h < K; h++) {
    if (max < arr[house[h]][n] + arr[n][house[h]]) {
      max = arr[house[h]][n] + arr[n][house[h]];
    }
  }
  if (min > max) {
    min = max;
    answer = [n];
  } else if (min === max) {
    answer.push(n);
  }
}

console.log(answer.sort((a, b) => a - b).join(" "));