🎲 백준 1507번 궁금한 민호

백준 1507번

🎨 참고 코드
💊 도시 a,b를 갈 때 다른 도시를 경유해서 갈 수 있다면 a,b간선을 없애줘도 되는 것이 포인트이다.

코드

const fs = require('fs'); 
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const min = input.map((el) => el.split(" ").map(Number));
const result = input.map((el) => el.split(" ").map(Number));

for (let k = 0; k < N; k++) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (i === k || k === j) continue;
      if (min[i][j] > min[i][k] + min[k][j]) return console.log(-1);
      if (min[i][j] === min[i][k] + min[k][j]) result[i][j] = 0;
    }
  }
}

let answer = 0;
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    answer += result[i][j];
  }
}
console.log(answer / 2);