@zzzc18
2017-11-09T16:51:36.000000Z
字数 965
阅读 974
模板库
深搜版 :如果更新 的时候两次经过一个点,那么一定有负环
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 200000+9;
const int MAXM = 200000+9;
struct E{
int next,to;
int val;
}edge[MAXM<<1];
int head[MAXN],edge_num;
int n,m;
bool pd;
bitset<MAXN> vis;
int dis[MAXN];
void addedge(int x,int y,int v){
edge[++edge_num].next=head[x];
edge[edge_num].to=y;
edge[edge_num].val=v;
head[x]=edge_num;
}
void SPFA(int x){
if(pd)return;
vis[x]=1;
for(int i=head[x];i;i=edge[i].next){
if(pd)return;
if(dis[x]+edge[i].val<dis[edge[i].to]){
dis[edge[i].to]=dis[x]+edge[i].val;
if(vis[edge[i].to]){
pd=1;
return;
}
SPFA(edge[i].to);
}
}
vis[x]=0;
}
void solve(){
for(int i=1;i<=n;i++){
SPFA(i);
if(pd){puts("YE5");return;}
}
puts("N0");
}
int main(){
int kase;
scanf("%d",&kase);
while(kase--){
memset(head,0,sizeof(head));
vis.reset();
memset(dis,0,sizeof(dis));
edge_num=0;
pd=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
if(c>=0)addedge(b,a,c);
}
solve();
}
return 0;
}