SPFA 差分约束 80分求助

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define eps 1e-8
const int inf=0x3f3f3f3f;
const int Maxn=100010;
const int Maxm=400010;
int n,k;
int S;
int head[Maxn],tot;
struct Edge{
	int to;
	int w;
	int nxt;
}E[Maxm];
void addedge(int u,int v,int w)
{
	tot++;
	E[tot].to=v;
	E[tot].w=w;
	E[tot].nxt=head[u];
	head[u]=tot;
}
int dis[Maxn],deg[Maxn];
bool vis[Maxn];
//class Queue{
//	private:
//		int st[500010];
//		int Front,Tail;
//		int siz;
//	public:
//		bool empty()
//		{
//			return siz==0;
//		}
//		void clear()
//		{
//			memset(st,0,sizeof(st));
//			Front=1;
//			Tail=0;
//			siz=0;
//		}
//		void push(int x)
//		{
//			st[++Tail]=x;
//			siz++;
//		}
//		void pop()
//		{
//			st[Front++]=0;
//			siz--;
//		}
//		int front()
//		{
//			return st[Front];
//		}
//}q;
bool spfa(int S)
{
//	memset(dis,0x3f,sizeof(dis));
	deque<int> q;
	dis[S]=0;
	vis[S]=1;
	q.push_back(S);
	deg[S]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(int i=head[u];i;i=E[i].nxt)
		{
			int v=E[i].to,w=E[i].w;
			if(dis[v]<dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(++deg[v]>=n)
				{
					return false;
				}
				if(!vis[v])
				{
					vis[v]=true;
					q.push_back(v);
				}
				
			}
		}
	}
	
	return true;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	S=0;
	for(int i=1;i<=k;i++)
	{
		int x,a,b;
		scanf("%lld%lld%lld",&x,&a,&b);
		switch(x)
		{
			case 1:{
				//Xa=Xb  ==> Xa-Xb<=0,Xa-Xb>=0 
				addedge(a,b,0);
				addedge(b,a,0);
				break;
			}
			case 2:{
				//Xa<Xb ==> Xa-Xb<=-1
				addedge(a,b,1);
				break;
			}
			case 3:{
				//Xa>=Xb ==> Xb-Xa<=0
				addedge(b,a,0);
				break;
			}
			case 4:{
				//Xa>Xb ==> Xb-Xa<0 Xb-Xa<=-1
				addedge(b,a,1);
				break;
			}
			default:{
				//Xa<=Xb ==> Xa-Xb<=0
				addedge(a,b,0); 
				break;
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		addedge(S,i,1);
	}
	if(!spfa(S))
	{
		puts("-1");
	}else{
		int ans=0;
		for(int i=1;i<=n;i++)
		{
//			cout<<dis[i]<<" ";
			ans+=dis[i];
		}
//		cout<<endl;
		printf("%lld\n",ans);
	}
	return 0;
}

//a[u]-a[v]<=w:
//u->v: -w
//Calculate Longest Path