题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
寻找一个从顶点1所能到达的负环，负环定义为：一个边权之和为负的环。
输入输出格式
输入格式：
第一行一个正整数T表示数据组数，对于每组数据：
第一行两个正整数N M，表示图有N个顶点，M条边
接下来M行，每行三个整数a b w，表示a->b有一条权值为w的边（若w<0则为单向，否则双向）
输出格式：
共T行。对于每组数据，存在负环则输出一行"YE5"(不含引号)，否则输出一行"N0"(不含引号)。
输入输出样例
输入样例#1：
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
输出样例#1：
N0
YE5
说明
n≤2000
m≤3000
−10000≤w≤10000
T≤10建议复制输出格式中的字符串。 本题数据感谢@negiizhao的精心构造，请不要使用玄学算法 本题数据有更新
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
long long read()
{
long long x=,f=;
char ch=getchar();
while(ch>''||ch<'')
{
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
const int maxn=;
const int maxm=;
int T,st=,n,m,num;
bool flag;
bool vis[maxn];
int dis[maxn],cnt[maxn],head[maxn],q[maxn];
struct node
{
int v,w,nxt;
} e[maxm*];
void add(int x,int y,int z)
{
e[++num].v=y;
e[num].w=z;
e[num].nxt=head[x];
head[x]=num;
}
bool spfa()
{
int l=,r=;
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
memset(cnt,,sizeof(cnt));
memset(q,,sizeof(q));
vis[st]=;
cnt[st]=;
dis[st]=;
q[r++]=st;
while(l!=r)
{
int u=q[l++];
if(l>n)
l=;
vis[u]=false;
for(int i=head[u]; i; i=e[i].nxt)
{
if(dis[e[i].v]>dis[u]+e[i].w)
{
dis[e[i].v]=dis[u]+e[i].w;
cnt[e[i].v]=cnt[u]+;
if(cnt[e[i].v]>=n&&e[i].w<)
return ;
if(!vis[e[i].v])
{
vis[e[i].v]=;
if(dis[e[i].v]>dis[q[l]])
{
l--;
if(l<)
l=n;
q[l]=e[i].v;
}
else
{
q[r++]=e[i].v;
if(r>n)
r=;
}
}
}
}
}
return false;
}
int main()
{
T=read();
while(T--)
{
n=read(),m=read();
memset(head,,sizeof(head));
num=;
for(int i=; i<=m; i++)
{
int x=read(),y=read(),w=read();
add(x,y,w);
if(w>=)
add(y,x,w);
}
if(spfa())
printf("YE5\n");
else
printf("N0\n");
}
return ;
}