什么是差分约束系统？
百度百科
如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
具体怎么实现？
前置技能（简而言之就是单源最短路径）
①链式前向星建图或者vector建图（这个好像用邻接矩阵也可以）
②SPFA
如何建图？
①先看题目要求求什么，求最大值那么就是跑最短路，求最小值那么就是跑最长路
怎么跑最长路？
只需要将SPFA中的符号反向即可，并且把inf设置成-inf
②看清楚求的是什么了之后还得看符号。首先所有转换的符号必须是带等于号的，也就是说必须是≥≤才可以，＞＜那么就不行（这个还需要特殊转换，稍后再讲）
③如果求最大值，也就是最短路那么符号必须统一成≤，如果有a-b<c那么变成 a-b<=c-1。如果有≥，那么就两边乘以负号例如 b-a>=c->a-b<=-c
④如果求最小值，也就是最长路转换格式同④
⑤如果要判断解是不是存在那就是SPFA判断是否存在负环，具体做法是在要入队的那一步加一个辅助数组计数，如果一个点入队次数超过总的点的个数，那么就不存在解了。
if(!bk[G[p][i].to])
{
bk[G[p][i].to]=1;
if(++vis[G[p][i].to]>n)
return cout<<-1,0;
q.push(G[p][i].to);
}
⑥最终按照第二个数为源点第一个数为去的点，第三个数为权值建图即可即
a-b>=c
等价于
G[b].push_back((node){a,c});
如何找答案？
直接输出dis数组即可
完整代码（Layout POJ - 3169 ）
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct node
{
int to,cost;
};
vector<node> G[10000];
long long dis[10000],bk[10000],vis[10000];
const int inf=INT_MAX;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,t1,t2;
cin>>n>>t1>>t2;
while(t1--)
{
int k1,k2,k3;
cin>>k1>>k2>>k3;
G[k1].push_back((node){k2,k3});
}
while(t2--)
{
int k1,k2,k3;
cin>>k1>>k2>>k3;
G[k2].push_back((node){k1,-k3});
}
for(int i=1;i<=n;i++)
dis[i]=i==1?0:inf;
queue<int> q;
q.push(1);
while(q.size())
{
int p=q.front();
q.pop();
bk[p]=0;
for(int i=0;i<G[p].size();i++)
{
if(dis[G[p][i].to]>dis[p]+G[p][i].cost)
{
dis[G[p][i].to]=dis[p]+G[p][i].cost;
if(!bk[G[p][i].to])
{
bk[G[p][i].to]=1;
if(++vis[G[p][i].to]>n)
return cout<<-1,0;
q.push(G[p][i].to);
}
}
}
}
if(dis[n]<INT_MAX)
cout<<dis[n];
else
cout<<-2;
}