rt，本人一开始的90pts代码，WA#1，主要是因为在输入的时候避免了自环。

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2e3+10,M=3e3+10;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
struct Edge{int u,v,w;}edges[2*M];
int n,m,vis[N],dis[N],cnt[N];
int head[N],nxt[2*M],idx=0;
void add_edge(int u,int v,int w){edges[++idx]=(Edge){u,v,w};nxt[idx]=head[u];head[u]=idx;}
int spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	memset(vis,0,sizeof(vis));
	queue<int> Q;
	Q.push(s);
	vis[s]=1,dis[s]=0;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		vis[u]=0;
		for(int j=head[u];~j;j=nxt[j]){
			int v=edges[j].v,w=edges[j].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)return 1;
				if(!vis[v]){Q.push(v);vis[v]=1;}
			}
		}
	}
	return 0;
}
void solve(){
	memset(head,-1,sizeof(head));idx=0;
	n=read(),m=read();
	FOR(i,1,m){
		int u=read(),v=read(),w=read();
		if(u!=v&&w>=0)add_edge(u,v,w),add_edge(v,u,w);
		else if(u!=v)add_edge(u,v,w);
	}
	printf("%s\n",spfa(1)?"YES":"NO");
}
int main(){
	int T=read();
	while(T--)solve();
	return 0;
}

后来又加了个特判，然后只有20pts

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2e3+10,M=3e3+10;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
struct Edge{int u,v,w;}edges[2*M];
int n,m,vis[N],dis[N],cnt[N];
int head[N],nxt[2*M],idx=0;
void add_edge(int u,int v,int w){edges[++idx]=(Edge){u,v,w};nxt[idx]=head[u];head[u]=idx;}
int spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	memset(vis,0,sizeof(vis));
	queue<int> Q;
	Q.push(s);
	vis[s]=1,dis[s]=0;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		vis[u]=0;
		for(int j=head[u];~j;j=nxt[j]){
			int v=edges[j].v,w=edges[j].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)return 1;
				if(!vis[v]){Q.push(v);vis[v]=1;}
			}
		}
	}
	return 0;
}
void solve(){
	memset(nxt,0,sizeof(nxt));memset(head,-1,sizeof(head));idx=0;
	n=read(),m=read();
	FOR(i,1,m){
		int u=read(),v=read(),w=read();
		if(u!=v&&w>=0)add_edge(u,v,w),add_edge(v,u,w);
		else if(u!=v)add_edge(u,v,w);
		if(u==v&&w<0){printf("YES\n");return;}
	}
	printf("%s\n",spfa(1)?"YES":"NO");
}
int main(){
	int T=read();
	while(T--)solve();
	return 0;
}

最后索性删掉了。就AC了。

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2e3+10,M=3e3+10;
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
struct Edge{int u,v,w;}edges[2*M];
int n,m,vis[N],dis[N],cnt[N];
int head[N],nxt[2*M],idx=0;
void add_edge(int u,int v,int w){edges[++idx]=(Edge){u,v,w};nxt[idx]=head[u];head[u]=idx;}
int spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	memset(vis,0,sizeof(vis));
	queue<int> Q;
	Q.push(s);
	vis[s]=1,dis[s]=0;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		vis[u]=0;
		for(int j=head[u];~j;j=nxt[j]){
			int v=edges[j].v,w=edges[j].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)return 1;
				if(!vis[v]){Q.push(v);vis[v]=1;}
			}
		}
	}
	return 0;
}
void solve(){
	memset(nxt,0,sizeof(nxt));memset(head,-1,sizeof(head));idx=0;
	n=read(),m=read();
	FOR(i,1,m){
		int u=read(),v=read(),w=read();
		if(w>=0)add_edge(u,v,w),add_edge(v,u,w);
		else add_edge(u,v,w);
	}
	printf("%s\n",spfa(1)?"YES":"NO");
}
int main(){
	int T=read();
	while(T--)solve();
	return 0;
}

这是怎么回事