타임머신

벨만포드

• 음수 가중치인 경우에 사용 가능하고(방향이 존재), 음수 사이클이 없다는 존재 하에 한 정점에서 다른 정점까지의 최단 거리를 구할 수 있는 알고리즘
• 모든 정점을 방문하면서 최단거리로 갱신
• 음의 사이클이 없는 경우 다시 간선들에 대해서 최단거리를 구하면 거리에 대한 갱신이 이루어지지 않음

문제풀이

• 각 정점들의 최단거리를 구함.
• 최단거리를 구한 후 다시 한번더 간선들에 대해서 루프를 돌림(음의 가중치가 있는지 판단)

소스코드

const log = console.log;
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// const input = fs.readFileSync("./stdin").toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(e => +e);
const paths = input.slice(1, M+1).map(e => e.split(" ").map(el => +el));
const visited = Array(N+1).fill(Infinity);
visited[1] = 0;

for(let i=1 ; i<=N ; i++){
  for(let j=0 ; j<paths.length ; j++){
    const [start, end, cost] = paths[j];
    if(visited[start] === Infinity) continue;
    const d = visited[start] + cost;
    if(visited[end] > d) visited[end] = d;
  }
}

for(let i=0 ; i<paths.length ; i++){
  const [start, end, cost] = paths[i];
  if(visited[start] === Infinity) continue;
  const d = visited[start] + cost;
  if(visited[end] > d){
    log(-1);
    return;
  }
}

for(let i=2 ; i<visited.length ; i++){
  visited[i] !== Infinity ? log(visited[i]) : log(-1);
}

참고

• 벨만포드(https://cloge.tistory.com/27)