介绍下差分约束系统：就是多个2未知数不等式形如（a-b<=k)的形式
问你有没有解，或者求两个未知数的最大差或者最小差
转化为最短路（或最长路）
1：求最小差的时候，不等式转化为b-a>=k的标准形式建图，求最长路
2：求最大差的时候，不等式转化为b-a<=k的标准形式建图，求最短路
然后具体的写的好的博客以供大家参考
1 http://www.cnblogs.com/void/archive/2011/08/26/2153928.html
2 http://blog.csdn.net/zhang20072844/article/details/7788672
3 http://www.cnblogs.com/pony1993/archive/2012/09/01/2666996.html
注：由于spfa比较慢，所以全是正权的时候用dij，负权用spfa，写spfa的时候，有时候用堆栈写起来更快（我也不知道为啥，当然手写的更快）
代码：
#include#include #include #include #include #include #include using namespace std;typedef long long LL;const int N=1e3+5;const int INF=0x3f3f3f3f;struct Edge{ int v,w,next;}edge[12000];bool inq[N];int tot,n,ml,md,head[N],d[N],cnt[N];void add(int u,int v,int w){ edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++;}queue q;bool spfa(int s){ for(int i=1;i<=n;++i) d[i]=INF,cnt[i]=0,inq[i]=0; while(!q.empty())q.pop(); d[s]=0; q.push(s),cnt[s]=1,inq[s]=true; while(!q.empty()){ int u=q.front(); q.pop(); inq[u]=false; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(d[v]>d[u]+edge[i].w){ d[v]=d[u]+edge[i].w; if(!inq[v]){ q.push(v); inq[v]=1; ++cnt[v]; if(cnt[v]>n)return false; } } } } return true;}int main(){ scanf("%d%d%d",&n,&ml,&md); memset(head,-1,sizeof(head)); for(int i=1;i<=ml;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } for(int i=1;i