[백준][밸만포드] 11657 타임머신 NodeJs 구현

목차

 

문제

https://www.acmicpc.net/problem/11657

 

 

구현 시 주의점

출발 노드 s에서 어떤 노드로의 경로가 존재하지 않음을 의미한다.

이 경우, 해당 간선을 통해 다른 노드 t로 이동하는 연산을 수행할 필요가 없다.

 

 

참고

https://yabmoons.tistory.com/365

[ 벨만포드 알고리즘 ] 개념과 구현방법 (C++)

 

 

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [N, M] = input[0].trim().split(" ").map(Number);
let INF = 999999999;
let arr = [];
let idx = 1;
let d = Array(501).fill(INF);
while (idx < input.length) {
  arr.push(input[idx].trim().split(" ").map(Number));
  idx++;
}
d[1] = 0;
for (let i = 1; i <= N; i++) {
  for (let j = 0; j < M; j++) {
    let s = arr[j][0];
    let t = arr[j][1];
    let cost = arr[j][2];
    if(d[s] === INF)continue;   //이 부분 없으면 틀림
    if (d[t] > cost + d[s]) {
      d[t] = cost + d[s];
      if (i === N) {   // N일때도 갱신하면 무한 루프가 존재한다.
        console.log(-1);
        return;
      }
    }
  }
}
for (let i = 2; i <= N; i++) {
  if (d[i] === INF) console.log(-1);  //INF라는 건 방문을 하지 못한다.
  else console.log(d[i]);
}