相比队列版spfa，除了#9从100ms变成了2s+，其它点都变快了很多，尤其是#10，从200ms变成了10ms。

所以说把队列换成优先队列的spfa到底对不对？或者说在什么情况下对？复杂度又该怎么分析？

以下是我的优先队列版spfa代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
#define ll long long 
#define db double
#define inf 0x3f3f3f3f
#define rep(i,x,y) for(ll i=(x);i<=(y);i++)
#define pll pair<int,int>
int n,m,b,cnt,T,head[N],t[N];
ll d[N];
struct node{
	int id,val;
}; 
bool operator<(node a,node b){
	return a.val>b.val;
}
int read(void)
{
	int x=0,f=1;char s;
	s=getchar();
	while(s>'9'||s<'0'){
		if(s=='-')f=-1;
		s=getchar(); 
	}
	while(s<='9'&&s>='0'){
		x=x*10+s-'0';
		s=getchar(); 
	}
	x*=f;
	return x;
}
bool vis[N];
struct EDGE{
	int v,w,next;
}edge[N*3];
void add(int u,int v,int w){
	edge[++cnt].next=head[u];
	head[u]=cnt;
	edge[cnt].v=v;
	edge[cnt].w=w;
}
bool spfa(int s){
	priority_queue<node>q;
	q.push(node{s,0});
	d[s]=0;
	vis[s]=1;
	while(!q.empty()){
		int x=q.top().id;
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=edge[i].next){
			if(d[edge[i].v]>d[x]+edge[i].w){
				d[edge[i].v]=d[x]+edge[i].w;
				if(!vis[edge[i].v])
				{
					t[edge[i].v]=t[x]+1;
					if(t[edge[i].v]>n)return 1;
					q.push(node{edge[i].v,d[edge[i].v]});
					vis[edge[i].v]=1;
				}
			}
		}
	}
	return 0;
}
int main()
{
	T=read();
	while(T--){
		n=read(),m=read();
		memset(edge,0,sizeof(edge));
		rep(i,1,n)d[i]=inf,vis[i]=0,t[i]=0,head[i]=0;
		cnt=0;
		rep(i,1,m){
			int u,v,w;
			u=read(),v=read(),w=read();
			if(w>=0)add(u,v,w),add(v,u,w);
			else add(u,v,w);
		}
		if(spfa(1))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}