题目描述
暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索
输入输出格式
输入格式：
第一行一个正整数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,M,|w|≤200 000；1≤a,b≤N；T≤10 建议复制输出格式中的字符串。
此题普通Bellman-Ford或BFS-SPFA会TLE
spfa判负环模板
判断有无负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 200010
using namespace std;
bool vis[N],vist;
int n,m,t,x,y,z,tot,head[N],dis[N];
int read()
{
,f=; char ch=getchar();
; ch=getchar();}
+ch-'; ch=getchar();}
return x*f;
}
struct Edge
{
int to,dis,from,next;
}edge[N<<];
int add(int x,int y,int z)
{
tot++;
edge[tot].to=y;
edge[tot].dis=z;
edge[tot].next=head[x];
head[x]=tot;
}
void begin()
{
tot=vist=;
memset(dis,,sizeof(dis));
memset(head,,sizeof(head));
memset(vis,false,sizeof(vis));
}
int spfa(int s)
{
vis[s]=true;
for(int i=head[s];i;i=edge[i].next)
{
int t=edge[i].to;
if(dis[s]+edge[i].dis<dis[t])
{
dis[t]=dis[s]+edge[i].dis;
if(vis[t]||vist)
{
vist=true;
break;
}
spfa(t);
}
}
vis[s]=false;
}
int main()
{
t=read();
while(t--)
{
n=read(),m=read();begin();
;i<=m;i++)
{
x=read(),y=read(),z=read();
add(x,y,z);
) add(y,x,z);
}
;i<=n;i++)
{
spfa(i);
if(vist) break;
}
if(vist) printf("YE5\n");
else printf("N0\n");
}
;
}