백준 node.js 11657번 타임머신 벨만-포드 알고리즘 JavaScript JS

 

11657번: 타임머신

기본적인 밸만 포드 알고리즘 문제입니다.

각 노드에서 모든 간선을 순회하며 모든 노드를 순회하는 O^2의 시간복잡도를 가집니다.

정확하게는 출발노드를 제외한 N-1개의 노드에서 E개의 간선을 순회하여 NE의 시간복잡도를 가집니다

문제풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
// 도시의 개수 N, 버스 노선의 개수 M
const [N,M] = input[0].split(" ").map(Number);

// 모든 간선들을 roads 배열에 넣기
const roads = [];
for(let i=1; i<=M; i++){
  const [str,end,time] = input[i].split(" ").map(Number)
  roads.push({str,end,time})
}

// 밸만-포드 알고리즘
const timeArr = Array.from({length : N+1}, () => Infinity)
timeArr[1] = 0;

for(let i=1; i<=M; i++){
  for(let {str,end,time} of roads){
    if(timeArr[str] + time < timeArr[end]){
      timeArr[end] = timeArr[str] + time
    }
  }
}

let pass = true;
A : for(let i=1; i<=M; i++){
  for(let {str,end,time} of roads){
    if(timeArr[str] + time < timeArr[end]){
      pass = false;
      break A;
    }
  }
}
if(pass){
  console.log(timeArr.slice(2).map(v => v === Infinity ? -1 : v).join("\\n"))
}else console.log(-1)