题目：http://poj.org/problem?id=1201
差分约束裸套路：前缀和
本题可以不把源点向每个点连一条0的边，可以直接把0点作为源点。这样会快许多！
可能是因为 i-1 向 i 都连着一条0的边。
别忘了约束条件不仅有s[ i ] - s[ i-1 ] >= 0，还有s[ i ] - s[ i - 1] <= 1！
别忘了s的范围不是n而是mx！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=5e4+;
int n,hd[N],xnt,dis[N],mx;
bool vis[N];
queue<int> q;
struct Ed{
int nxt,to,w;
Ed(int n=,int t=,int w=):nxt(n),to(t),w(w) {}
}ed[N<<];
void add(int x,int y,int z)
{
ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt;
}
void spfa()
{
memset(dis,-,sizeof dis);dis[]=;
q.push();vis[]=;
while(q.size())
{
int k=q.front();q.pop();vis[k]=;
for(int i=hd[k],v;i;i=ed[i].nxt)
if(dis[k]+ed[i].w>dis[v=ed[i].to])
{
dis[v]=dis[k]+ed[i].w;
if(!vis[v])vis[v]=,q.push(v);
}
}
}
int main()
{
scanf("%d",&n);int x,y,z;
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x-,y,z);mx=max(mx,y);
}
for(int i=;i<mx;i++)add(i,i+,),add(i+,i,-);
spfa();printf("%d",dis[mx]);
return ;
}