注意 SPFA 使用松弛次数判负环是不正确的：

if(d[v] > d[u]+w) {
		d[v] = d[u]+w;
		if(++cnt[v] >= n)	return true;
		...
	}

使用最短路经过边数判负环是正确的：

if(d[v] > d[u]+w) {
	d[v]=d[u]+w, cnt[v]=cnt[u]+1;
	if(cnt[v] >= n)	return true;
	if(!vis[v]) {
		vis[v] = 1;
		q.push(v);
	}
}

因为最短路最多经过 $n$ 个点，即 $n-1$ 条边，若经过边数 $\gt n$ 则说明存在负环。