http://poj.org/problem?id=1201
题目大意：
有一个序列，题目用n个整数组合 [ai，bi，ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。
思路：
设s[i]为从1~i的整数个数。
这样对于区间[ a , b]显然有 S[b] - S[a-1] >=c[i] （为什么是a-1?因为闭区间a也要选上呀）
然后还有
0<= S[B]-S[B-1] <=1 （整数的话最多比前一个大一，好吧，我大二- -|||我不二啊！！）
变形得：
S[B]-S[B-1] >=0
S[B-1]-S[B]>=-1
然后图就可以建立出来啦~~~~
老样子，我也加了一个点连接到所有的点（为什么？见我上一篇http://blog.csdn.net/murmured/article/details/18780557）
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=50000+10;
const int MAXM=500000;
const int INF=-100000000;
struct edge
{
int to;
int val;
int next;
}e[MAXM];
int head[MAXN],len,n,m,c,start,dis[MAXN];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
bool vis[MAXN];
void spfa()
{
for(int i=start;i<=n;i++)
{
dis[i]=INF;
vis[i]=0;
}
queue<int> q;
dis[0]=0;
vis[0]=true;
q.push(0);
while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=false;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[cur] + e[i].val > dis[id])
{
dis[id]=dis[cur]+e[i].val;
if(!vis[id])
{
vis[id]=true;
q.push(id);
}
}
}
}
}
int main()
{
while(~scanf("%d",&m))
{
len=0;
memset(head,-1,sizeof(head));
n=0;
start=9999999;
for(int i=1;i<=m;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from-1,to,val);
if(to >n) n=to;
if(start > from) start=from;
}
for(int i=start;i<=n;i++)
{
add(0,i,0);
add(i,i-1,-1);
add(i-1,i,0);
}
spfa();
printf("%d\n",dis[n]);
}
return 0;
}