最小值求最长路。
最大值求最短路。
发现每个约束条件可以转化为一条边，表示一个点到另外一个点至少要加上一个定值。
限定了每一个值得取值下界，然后最长路求出答案即可。
差分约束系统，感觉上更像是两个变量之间约束的线性规划问题。
想了想怎么可能有-1的情况，原来2、4操作中a、b相同的时候会造成一个环
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define mp make_pair
#define maxn 800005 int n,k,flag=0;
int h[maxn],to[maxn],ne[maxn],en=0,w[maxn],inq[maxn],tim[maxn];
queue <int> q;
ll dis[maxn],ans; void add(int a,int b,int c)
{
to[en]=b;ne[en]=h[a];w[en]=c;h[a]=en++;
} void SPFA()
{
memset(dis,-1,sizeof dis);
dis[0]=0;inq[0]=1;q.push(0);tim[0]++;
while (!q.empty())
{
int x=q.front(); q.pop(); inq[x]=0;
for (int i=h[x];i>=0;i=ne[i])
if (dis[to[i]]<dis[x]+w[i]){
dis[to[i]]=dis[x]+w[i];
if (!inq[to[i]])
{
inq[to[i]]=1;
tim[to[i]]++;
if (tim[to[i]]>n)
{
printf("-1\n");
return ;
}
q.push(to[i]);
}
}
}
F(i,1,n) ans+=dis[i];
printf("%lld\n",ans);
} int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&k);
F(i,1,k)
{
int x,a,b;scanf("%d%d%d",&x,&a,&b);
switch(x)
{
case 1: add(a,b,0);add(b,a,0);break;
case 2: add(a,b,1); if (a==b) flag=1; break;
case 3: add(b,a,0);break;
case 4: add(b,a,1); if (a==b) flag=1; break;
case 5: add(a,b,0);break;
}
}
D(i,n,1) add(0,i,1);
if (flag) {printf("-1\n");return 0;}
SPFA();
}