コード
let v = 0, e = 0, r = 0
let path = []
process.stdin.resume();
process.stdin.setEncoding("utf-8");
process.stdin.on("data", function (input) {
let num = 0
const lines = input.split("\n")
for (const line of lines) {
if (line === "") {
break
}
const m = line.split(" ").map(v => parseInt(v))
if (num === 0) {
v = m[0]
e = m[1]
r = m[2]
} else {
path.push(m)
}
num++
}
});
process.stdin.on("end", function () {
// console.log(v, e, r)
// console.log(path)
bellmanFord(v, r, path)
});
/**
* @param {number} v
* @param {number} r
* @param {number[][]} path
*/
function bellmanFord(v, r, path) {
const inf = Number.MAX_SAFE_INTEGER
const dist = Array(v).fill(inf)
dist[r] = 0
for (let i = 0; i < v; i++) {
let change = false
for (const [s, t, d] of path) {
if (dist[s] === inf) {
continue
}
if (dist[s] + d < dist[t]) {
if (i + 1 === v) {
console.log('NEGATIVE CYCLE')
return
}
dist[t] = dist[s] + d
change = true
} else {
continue
}
}
if (!change) {
break
}
}
for (const d of dist) {
console.log(d === inf ? 'INF' : d)
}
}
Top comments (0)