对于一个有向图，使用spfa判负环，条件不是一个点 $a_i$ 重复进入队列次数大于 $n$ ($n$ 为图中点数)吗？为什么我这题代码的spfa部分，会将没有负环的情况误判成有负环的情况，而仅仅是调整最多进队列次数就能得到正确答案，有没有大佬解释一下是什么原因？

错误代码(WA on #11)

#include<bits/stdc++.h>
#define maxn 3105
#define maxm 9105
using namespace std;
struct Edge
{
	int to,ne,w;
};
Edge edge[maxm];
int cnt,head[maxn],h[maxn];
int n,m;
void add(int x,int y,int w)
{
	cnt++;
	edge[cnt].to=y;
	edge[cnt].w=w;
	edge[cnt].ne=head[x];
	head[x]=cnt;
}
queue<int> q;
int jl[maxn];
bool spfa()
{
	q.push(0);
	for(int i=1;i<=n;i++)
	{
		h[i]=1;
	}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=edge[i].ne)
		{
			int y=edge[i].to,w=edge[i].w;
			if(h[x]+w<h[y])
			{
				h[y]=h[x]+w;
				jl[y]++;
				//if(x==2999)
				//{
				//	//cout<<"!!!";
				//}
				//if(y==2999)
				//{
				//	cout<<x<<" ";
				//}
				if(jl[y]>n+77)
				{
					//cout<<y<<" "<<jl[y];
					return true;
				}
				q.push(y);
			}
		}
	}
	return false;
}
int g[maxn];
bool done[maxn];
struct Pair
{
	int x,d;
	bool operator<(const Pair &p)const
	{
		return d>p.d;
	}
	Pair(int xx,int dd)
	{
		x=xx,d=dd;
	}
};
priority_queue<Pair> pr;
void dij(int x)
{
	memset(done,false,sizeof(done));
	for(int i=1;i<=n;i++)
	{
		g[i]=1000000000;
	}
	g[x]=0;
	pr.push(Pair(x,g[x]));
	while(!pr.empty())
	{
		int x=pr.top().x;
		pr.pop();
		if(done[x])
		{
			continue;
		}
		done[x]=true;
		for(int i=head[x];i;i=edge[i].ne)
		{
			int y=edge[i].to,w=edge[i].w;
			if(g[x]+w<g[y])
			{
				g[y]=g[x]+w;
				pr.push(Pair(y,g[y]));
			}
		}
	}
}
signed main()
{
	freopen("P5905_11.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		add(x,y,w);
	}
	for(int i=1;i<=n;i++)
	{
		add(0,i,0);
	}
	if(spfa())
	{
		cout<<-1<<"\n";
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=edge[j].ne)
		{
			int x=i,y=edge[j].to;
			edge[j].w+=h[x]-h[y];
		}
	}
	for(int i=1;i<=n;i++)
	{
		dij(i);
		long long ans=0;
		for(int j=1;j<=n;j++)
		{
			if(g[j]!=1000000000)
			{
				g[j]+=h[j]-h[i];
			}
			//cout<<g[j]<<" ";
			ans+=1ll*g[j]*j;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

正确代码(仅调整了第48行)

#include<bits/stdc++.h>
#define maxn 3105
#define maxm 9105
using namespace std;
struct Edge
{
	int to,ne,w;
};
Edge edge[maxm];
int cnt,head[maxn],h[maxn];
int n,m;
void add(int x,int y,int w)
{
	cnt++;
	edge[cnt].to=y;
	edge[cnt].w=w;
	edge[cnt].ne=head[x];
	head[x]=cnt;
}
queue<int> q;
int jl[maxn];
bool spfa()
{
	q.push(0);
	for(int i=1;i<=n;i++)
	{
		h[i]=1;
	}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=edge[i].ne)
		{
			int y=edge[i].to,w=edge[i].w;
			if(h[x]+w<h[y])
			{
				h[y]=h[x]+w;
				jl[y]++;
				//if(x==2999)
				//{
				//	//cout<<"!!!";
				//}
				//if(y==2999)
				//{
				//	cout<<x<<" ";
				//}
				if(jl[y]>n+78)
				{
					//cout<<y<<" "<<jl[y];
					return true;
				}
				q.push(y);
			}
		}
	}
	return false;
}
int g[maxn];
bool done[maxn];
struct Pair
{
	int x,d;
	bool operator<(const Pair &p)const
	{
		return d>p.d;
	}
	Pair(int xx,int dd)
	{
		x=xx,d=dd;
	}
};
priority_queue<Pair> pr;
void dij(int x)
{
	memset(done,false,sizeof(done));
	for(int i=1;i<=n;i++)
	{
		g[i]=1000000000;
	}
	g[x]=0;
	pr.push(Pair(x,g[x]));
	while(!pr.empty())
	{
		int x=pr.top().x;
		pr.pop();
		if(done[x])
		{
			continue;
		}
		done[x]=true;
		for(int i=head[x];i;i=edge[i].ne)
		{
			int y=edge[i].to,w=edge[i].w;
			if(g[x]+w<g[y])
			{
				g[y]=g[x]+w;
				pr.push(Pair(y,g[y]));
			}
		}
	}
}
signed main()
{
	freopen("P5905_11.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		add(x,y,w);
	}
	for(int i=1;i<=n;i++)
	{
		add(0,i,0);
	}
	if(spfa())
	{
		cout<<-1<<"\n";
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=edge[j].ne)
		{
			int x=i,y=edge[j].to;
			edge[j].w+=h[x]-h[y];
		}
	}
	for(int i=1;i<=n;i++)
	{
		dij(i);
		long long ans=0;
		for(int j=1;j<=n;j++)
		{
			if(g[j]!=1000000000)
			{
				g[j]+=h[j]-h[i];
			}
			//cout<<g[j]<<" ";
			ans+=1ll*g[j]*j;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

仅调整了第48行，将 $n+77$ 改为 $n+78$，就正确了。 附上提交记录
正确
错误