AcWing 852. spfa判断负环(Javascript)
原题链接
简单
作者:
cp777
,
2021-03-02 16:14:12
,
所有人可见
,
阅读 236
let INF = 0x3f3f3f3f;
let N = 2010;
let M = 10010;
let idx = 0;
let head = new Int32Array(N).fill(-1);
let next = [];
let edge = [];
let w = [];
let dist = new Int32Array(N).fill(INF);
let queue = [];
let cnt = new Int32Array(N);
let st = new Int32Array(N);
let insert = (a, b, c) => {
edge[idx] = b;
w[idx] = c;
next[idx] = head[a];
head[a] = idx++;
}
/**
在原图的基础上新建一个虚拟源点0,从该点向其他所有点连一条权值为0的有向边。
那么原图有负环等价于新图有负环。此时在新图上做spfa,将虚拟源点加入队列中。
然后进行spfa的第一次迭代,这时会将所有点的距离更新并将所有点插入队列中。
*/
//cnt[i]:从虚拟点0到i点最短路径所经过的边
//不用dist的实际意义,不管dist数组的初值是多少,都是可以的。
//因为只要有负环存在,就必然有某些点的距离是负无穷,所以不管距离被初始化成何值,都一定严格大于负无穷,所以一定会被无限更新。
//只要存在负环,dist和cnt会不断变化,cnt达到n即得出结果
let spfa = () => {
for (let i = 1; i <= n; i++) {
queue.push(i);
st[i] = true;
}
while (queue.length) {
let top = queue.shift();
st[top] = false;
for (let i = head[top]; i !== -1; i = next[i]) {
let point = edge[i];
if (dist[point] > dist[top] + w[i]) {
dist[point] = dist[top] + w[i];
cnt[point] = cnt[top] + 1;
if (cnt[point] >= n) return true; //从0到该点经过n条边(不考虑0到每个点的距离),一共n个点,所以必然存在环,最短路径中只能是负环
if (!st[point]) {
queue.push(point);
st[point] = true;
}
}
}
}
return false;
}
let n = 0,
m = 0;
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
n = getInputNums(line)[0];
m = getInputNums(line)[1];
} else if (lineIdx <= m) {
let arr = getInputNums(line);
let a = arr[0];
let b = arr[1];
let c = arr[2];
insert(a, b, c);
if (lineIdx === m) {
let res = spfa();
if (res) console.log('Yes');
else console.log('No');
}
}
});
});