```cpp
/*
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
*/
#include<bits/stdc++.h>
#define itn int
#define el endl
#define db double
using namespace std;
long long n,m,u[2001],dis[2001],arr[2001];
bool flag=0;
queue<int> q;
struct node{
int to,w;
};
vector<node> e[2001];
void SPFA(){
int a;
while(!q.empty()){
a=q.front();
for(int i=0;i<e[a].size();i++){
if(dis[e[a][i].to]>dis[a]+e[a][i].w){
dis[e[a][i].to]=dis[a]+e[a][i].w;
if(u[e[a][i].to]==0){
if(++arr[e[a][i].to]>n){
cout<<"YES\n";
flag=1;
return;
}
u[e[a][i].to]=1;
q.push(e[a][i].to);
}
}
}
u[a]=0;
q.pop();
}
}
int main(){
int T;
cin>>T;
while(T--){
memset(u,0,sizeof(u));
memset(arr,0,sizeof(arr));
cin>>n>>m;
int a,b,c;
for(int i=0;i<m;i++){
cin>>a>>b>>c;
if(c>0)
e[b].push_back({a,c});
e[a].push_back({b,c});
}
for(int i=0;i<=n;i++){
dis[i]=INT_MAX;
}
dis[1]=0;
q.push(1);
u[1]=1;
SPFA();
if(!flag){
cout<<"NO\n";
}
for(int i=1;i<=n;i++){
while(!e[i].empty()){
e[i].pop_back();
}
}
while(!q.empty()){
q.pop();
}
}
system("pause");
return 0;
}
```
by Sunhaotian2011 @ 2024-03-15 20:44:58
记录放错了
[记录](https://www.luogu.com.cn/record/150985833)
by Sunhaotian2011 @ 2024-03-15 20:46:30
@[Sunhaotian2011](/user/969476) 你可以对照我的改一改
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,T,w,u,v,dis[(int)2e3+5],in[(int)2e3+5];
struct node{
int y,w;
};
bool vis[(int)2e3+5];
vector<node> nbr[(int)2e3+5];
bool spfa(int s){
queue<int> q;
for(int i=1;i<=n;i++){
dis[i]=inf;
in[i]=vis[i]=0;
}
dis[s]=0;
q.push(s);
vis[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=0;i<nbr[x].size();i++){
int y=nbr[x][i].y,w=nbr[x][i].w;
if(dis[x]+w<dis[y]){
dis[y]=dis[x]+w;
in[y]=in[x]+1;
if(in[y]>=n){
return 1;
}
if(!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
return 0;
}
signed main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
nbr[i].clear();
}
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
nbr[u].push_back((node){v,w});
if(w>=0){
nbr[v].push_back((node){u,w});
}
}
if(spfa(1)){
cout<<"YES";
}else{
cout<<"NO";
}
cout<<endl;
}
return 0;
}
```
by huangmingyisunny1804 @ 2024-03-15 20:47:53
@[huangmingyisunny1804](/user/966082) 好的,谢谢!已关!
by Sunhaotian2011 @ 2024-03-15 20:58:02