백준 node.js 1865번 웜홀 벨만-포드 알고리즘 JavaScript JS

 

1865번: 웜홀

이 문제는 벨만-포드 알고리즘을 이용하여 풀 수 있습니다.

일반적인 벨만-포드 문제와는 다르게, 각 노드에 도달할 수 있는 최소시간을 Infinity로 하면 풀리지 않습니다. 시작 노드가 모든 점이 될 수 있기 때문에 Infinity가 아닌 0으로 초기값을 넣어 줍니다.

문제풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split("\\n");

//테스트 케이스
const TC = input.shift();
for (let i = 0; i < TC; i++) {
  //정점, 도로, 웜홀 의 개수
  const [N, M, W] = input.shift().split(" ").map(Number);
  const road = input.splice(0, M);
  const wormhole = input.splice(0, W);

  const links = []
  for (let [str, end, time] of road.map((v) => v.split(" ").map(Number))) {
    links.push({str,end,time});
    links.push({ str: end, end: str, time});
  }
  for (let [str, end, time] of wormhole.map((v) => v.split(" ").map(Number))) {
    links.push({str,end,time:-time});
  }
	
	//Infinity가 아닌 0으로 초기값을 주었습니다.
  const nodes = Array(N+1).fill(0)
  for(let i=1; i<=N; i++){
    for(let {str,end,time} of links){
      if(nodes[str] + time < nodes[end]){
        nodes[end] = nodes[str] + time
      }
    }
  }
  let pass = "NO";
  A : for(let i=1; i<=N; i++){
    for(let {str,end,time} of links){
      if(nodes[str] + time < nodes[end]){
        pass = "YES";
        break A;
      }
    }
  }
  console.log(pass)
}