🎲 백준 1238번 파티

백준 1238번

🎨 참고
🎨 참고 코드

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [N, M, X] = input.shift().split(" ").map(Number);

const graph = Array.from(new Array(N + 1), () => []);
const result = new Array(N + 1);

for (let i = 0; i < M; i++) {
  const [s, e, v] = input[i].split(" ").map(Number);
  graph[s].push([e, v]);
}

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

let answer = 0;
for (let n = 1; n <= N; n++) {
  answer = Math.max(answer, result[n][X] + result[X][n]);
}

console.log(answer);