小K的农场 差分约束

#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
struct Edge{
	int v,w,nxt;
};
int cnt,head[100000];
Edge edge[100000];
int book[10005],dis[10005],indfs[100005],n,m;
int read(){
	int x=0,dign=1;
	char c = getchar();
	while(c<'0'||c>'9'){
		if(c=='-')dign=-1;
		c = getchar();
	}
	while(c>='0'&&c<='9'){
		x = x*10 + c - '0';
		c = getchar();
	}
	return x*dign;
}
void add(int u,int v,int w){
	cnt++;
	edge[cnt].v = v; edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
bool spfa(int u){
		indfs[u] = 1;
		for(int w,v,i=head[u];i;i=edge[i].nxt){
			v = edge[i].v; w = dis[u] + edge[i].w;
			if(!book[v]||dis[v]<w){
				if(indfs[v])return false;//一个点通过一段路径回到这个点比之前更优存在环 
				book[v] = 1;
				dis[v]=w;
				if(!spfa(v))return false;
			}	
		}
		indfs[u] = 0;
		return true; 
}
int main()
{
	n = read(); m = read();
	for(int i=0;i<=n;i++)add(0,i,0);
	
	for(int i=0;i<m;i++){
		int t,a,b,c;
		t = read();
		if(t==3){
			a = read(); b = read();
			add(b,a,0);
			add(a,b,0);
		}else if(t==1){
			a = read(); b = read(); c = read();
			add(b,a,c);
		}else{
			a = read(); b = read(); c = read();
			add(a,b,-c);	
		}
	}
	for(int i=1;i<=n;i++)dis[i] = -1;
	dis[0] = 0; book[0] = 1;

	if(!spfa(0))printf("No\n");
	else printf("Yes\n"); 
	return 0;
 }