差点就忘了还有差分约束这个东西……看见了就要学习一个
原题：
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
N<=100000，K<=100000，1<=A, B<=N
差分约束模板题，学习一个！
以操作3为例，如果a不少于b，那么a-b>=0，a>=b+0
所以连b到a权值为0的边，根据三角形不等式，要跑最长路来使条件满足
具体原理我也想不太清楚，反正记住搞出三角形不等式后跑符号相反的spfa就对了 _(:3 」∠)_
因为写出了像"q[tl]=false"酱sb的东西+没对拍所以没1A……
注意longlong
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
struct ddd{int nxt,y,v;}e[]; int lk[],ltp=;
inline void ist(int x,int y,int z){ e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z;}
int n,m;
int dstc[],cnt[];
int q[],hd=,tl=,tp=; bool vstd[];
bool spfa(){
memset(vstd,,sizeof(vstd));
//memset(dstc,0,sizeof(dstc));
for(int i=;i<=n;++i) q[++hd]=i,dstc[i]=;
while(tl!=hd){
tl=(tl==tp ? : tl+);
for(int i=lk[q[tl]];i;i=e[i].nxt)if(dstc[q[tl]]+e[i].v>dstc[e[i].y]){
dstc[e[i].y]=dstc[q[tl]]+e[i].v;
if(++cnt[e[i].y]==n) return false;
if(!vstd[e[i].y]) q[hd=(hd==tp ? : hd+)]=e[i].y,vstd[e[i].y]=true;
}
vstd[q[tl]]=false;
}
return true;
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n>>m;
int mk,l,r;
while(m--){
mk=rd(),l=rd(),r=rd();
if(mk==) ist(l,r,),ist(r,l,);
else if(mk==){
if(l==r){ cout<<-<<endl; return ;}
ist(l,r,);
}
else if(mk==) ist(r,l,);
else if(mk==){
if(l==r){ cout<<-<<endl; return ;}
ist(r,l,);
}
else if(mk==) ist(l,r,);
}
if(!spfa()){ cout<<-<<endl; return ;}
long long ans=;
for(int i=;i<=n;++i) ans+=dstc[i];
cout<<ans<<endl;
return ;
}