1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 #define MaxSize 50005
5 #define inf 0x7ffffff
6 struct edge{
7 int a,b,c;
8 }eg[MaxSize];
9 int n;
10 int d[MaxSize];
11 void bellman_Ford(int s,int e){
12 int i,j;
13 for(i=s;i<=e;i++)
14 d[i]=0;
15 //d[b]-d[a],由于b增加1过,因此,相当于d[a]为d[a-1],d[b]-d[a]的意义为[a,b]区间内符合条件的元素
16 for(i=s+1;i<e;i++){
17 bool flag=true;
18 for(j=0;j<n;j++)//约束条件,[a,b]区间内元素不少于c,即d[b]-d[a]>=c
19 if(d[eg[j].b]-eg[j].c<d[eg[j].a] )
20 d[eg[j].a]=d[eg[j].b]-eg[j].c,flag=false;
21 for(j=e;j>s;j--)
22 if(d[j]<d[j-1])//约束条件,[m,m+1],d[m]<=d[m+1]
23 d[j-1]=d[j],flag=false;
24 for(j=s+1;j<=e;j++)
25 if(d[j-1]+1<d[j])//d[m]+1>=d[m+1];
26 d[j]=d[j-1]+1,flag=false;
27 if(flag)
28 return;
29 }
30 }
31 int main(){
32 freopen("in.txt","r",stdin);
33 while (~scanf("%d",&n)){
34 int i,s,e;
35 s=inf;
36 e=-inf;
37 for(i=0;i<n;i++){
38 scanf("%d %d %d",&eg[i].a,&eg[i].b,&eg[i].c);
39 eg[i].b++;//考虑到可能在计算会用到a-1,而当a=0时就越界了,因此整体加一
40 if(eg[i].a<s)
41 s=eg[i].a;
42 if(eg[i].b>e)
43 e=eg[i].b;
44 }
45 bellman_Ford(s,e);
46 printf("%d\n",d[e]-d[s]);
47 }
48 return 0;
49 }
posted on 2012-07-26 21:46
Leo.W 阅读(383)
评论(0) 编辑 收藏 引用