题目
思路
用spfa求解，查询当前是否合法，正向加正边，反向加反边。记得判负环。
#include<bits/stdc++.h>
using namespace std;
const int maxm=500+10,maxn=4000+10;
int head[maxn],ver[maxm],edge[maxm],Next[maxm],tot;
void add(int x,int y,int z){
ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
int read(){
char c=getchar();
int x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int vis[maxn],dis[maxn];
int cnt[maxn];
bool flag=0;int n;
void spfa(int s){
queue<int>q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
dis[s]=0,vis[s]=1;
q.push(s);cnt[s]++;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=Next[i]){
int v=ver[i];
if(dis[v]>dis[u]+edge[i]){
dis[v]=dis[u]+edge[i];
if(!vis[v]){
cnt[v]++;
q.push(v);
vis[v]=1;
if(cnt[v]>n+1){
flag=1;
return;
}
}
}
}
}
}
int main(){
int t;t=read();
for(int tt=1;tt<=t;tt++){
tot=0;
memset(head,0,sizeof(head));
int m;
n=read(),m=read();
for(int i=1;i<=m;i++){
ver[i]=0,edge[i]=0,Next[i]=0;
}
n++;flag=0;
for(int i=1;i<=m;i++){
int l,r,w;
l=read(),r=read(),w=read();
r++;
spfa(l);
if(flag==1){
printf("false
");
break;
}
if(dis[r]>=1061109567){
add(l,r,w);
add(r,l,-w);
}
else{
if(dis[r]!=w){
printf("false
");
flag=1;
break;
}
}
}
if(!flag)printf("true
");
}
}