50pts差分约束

#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 5010
#define INF 0x3f3f3f3f
using namespace std;

template <typename T> il void Iput(T &x)
{
	char c;
	bool f = false;
	while((c=getchar())<'0' || c>'9')	if(c=='-')	f=true;
	x = c^48;
	while((c=getchar())>='0' && c<='9')	x = (x<<1) + (x<<3) + (c^48);
	if(f)	x = -x;
}

template <typename T> void Wri(T x)
{
	if(x > 9)	Wri(x/10);
	putchar(x%10^48);
}

template <typename T> void Oput(T x)
{
	if(x < 0)	putchar('-'), x=-x;
	Wri(x);
}

struct Edge {
	int x, nex, w;
}e[MAXN<<1];

int head[MAXN], tote;

il void ae(int u, int v, int w)
{
	e[++tote].x = v;
	e[tote].w = w;
	e[tote].nex = head[u];
	head[u] = tote;
}

int n, m;

int dis[MAXN];
const int MAXQ = 1<<12;
int q[MAXQ], l, r;
bool in_q[MAXN];
int len[MAXN], ctr[MAXN];

il bool spfa(int s)
{
	l = 1;
	r = 0;
	q[++r & MAXQ-1] = s;
	in_q[s] = true;
	dis[s] = 0;
	while(l<=r)
	{
		int u = q[l++ & MAXQ-1];
		in_q[u] = false;
		for(rg int i=head[u] ; i ; i=e[i].nex)
		{
			int v = e[i].x, w = e[i].w;
			if(dis[v] > dis[u]+w)
			{
				dis[v] = dis[u]+w;
				if(!in_q[v])
				{
					if(++ctr[v]>=n)	return true;
					if((len[v]=len[u]+1)>=n)	return true;
					q[++r & MAXQ-1] = v;
					in_q[v] = true;
				}
			}
		}
	}
	return false;
}

signed main()
{
	freopen("P1993_2.in", "r", stdin);
	
	Iput(n), Iput(m);
	for(rg int i=1 ; i<=m ; ++i)
	{
		int op, u, v, w;
		Iput(op), Iput(u), Iput(v);
		if(op == 1)	//dis[u] <= dis[v]-w
		{
			Iput(w);
			ae(v, u, -w);
		}
		else if(op == 2)	//dis[u] <= dis[v]+w
		{
			Iput(w);
			ae(v, u, w);
		}
		else if(op == 3)	//dis[u] == dis[v]
		{
			ae(u, v, 0);
			ae(v, u, 0);
		}
	}
	memset(dis, 0x3f, sizeof dis);
	for(rg int i=1 ; i<=n ; ++i)
		if(dis[i] == INF)
			if(spfa(i))
			{
				printf("No\n");
				return 0;
			}
	printf("Yes\n");
	
	return 0;
}