题目链接：http://poj.org/problem?id=3159
题目大意：给n个人派糖果，给出m组数据，每组数据包含A，B，C三个数，意思是A的糖果数比B少的个数不多于C,即B的糖果数 - A的糖果数<=C 。
最后求n 比 1 最多多多少颗糖果。
解题思路：经典差分约束的题目，具体证明看这里《数与图的完美结合——浅析差分约束系统》。
不妨将糖果数当作距离，把相差的最大糖果数看成有向边AB的权值，我们得到 dis[B]-dis[A]<=w(A,B)。看到这里，我们可以联想到求最短路时的松弛操作，
当if(dis[B]>dis[A]+w(A,B)因为要使A，B间满足dis[B]-dis[A]<=w(A,B)右要使差值最大，所以dis[B]=dis[A]+w(A,B)。
所以这题可以转化为最短路来求。注意：很坑，这题的spfa被卡了，要用栈才不会超时。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
const int N=2e5+; struct node{
int to,next,w;
}edge[N]; int n,m;
int idx,head[N];
//初始化
void init(){
idx=;
memset(head,-,sizeof(head));
}
//添加边
void addEdge(int u,int v,int w){
edge[idx].to=v;
edge[idx].w=w;
edge[idx].next=head[u];
head[u]=idx;
idx++;
} int dis[N];
bool vis[N];
void spfa(int s){
memset(dis,0x3f,sizeof(dis));
dis[s]=;
stack<int>sk;
sk.push(s);
while(!sk.empty()){
int k=sk.top();
sk.pop();
vis[k]=false;
for(int i=head[k];i!=-;i=edge[i].next){
node t=edge[i];
//改变了松弛条件
if(dis[t.to]>dis[k]+t.w){
dis[t.to]=dis[k]+t.w;
if(!vis[t.to]){
sk.push(t.to);
vis[t.to]=true;
}
}
}
}
} int main(){
init();
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
addEdge(a,b,w);
}
spfa();
printf("%d\n",dis[n]-dis[]);
return ;
}