zoj 1508 Intervals

/*
  Name: zoj 1508 Intervals
  Author: Unimen
  Date: 25/08/11 20:50
  Description:      
*/

/*
    ：  06     
  ：       ，               ，          ，     ，
           ，              ，          

  ：   dis    0，   dis[Edge[i].b] < dis[Edge[i].a] + Edge[i].w，         ，
        
*/

#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 50010;

struct 
{
	int a, b, w;
}Edge[MAX];
int n;
int dis[MAX];
int iMax, iMin;

int bellman_ford()
{
	int i;
	bool bUpdate = true;
	while(bUpdate)
	{
		bUpdate = false;
		for(i=1; i<=n; ++i)
		{
			if(dis[Edge[i].b] < dis[Edge[i].a] + Edge[i].w)
			{
				dis[Edge[i].b] = dis[Edge[i].a] + Edge[i].w;
				bUpdate = true;
			}
		}
		
		for(i=iMax; i>=iMin; --i)
		{
			if(dis[i-1] < dis[i] - 1)
			{
				dis[i-1] = dis[i] - 1;
				bUpdate = true;
			}
		}
		
		for(i=iMin; i<=iMax; ++i)
		{
			if(dis[i] < dis[i-1])
			{
				dis[i] = dis[i-1];
				bUpdate = true;	
			}
		}
		
		
	}
	return dis[iMax] - dis[iMin-1];	  //   
}

int main()
{
	int i;
	while(cin>>n)
	{
		iMax = 0, iMin = 1000000000;
		
		//     
		for(i=1; i<=n; ++i)
		{
			int a, b, w;
			cin>>a>>b>>w;
			Edge[i].a = a - 1;
			Edge[i].b = b;
			Edge[i].w = w;
			if(iMax < b)
				iMax = b;
			if(iMin > a)
				iMin = a;
		}
		memset(dis, 0, sizeof(dis)); //        0，        0	
		cout<<bellman_ford()<<endl;
	}
	return 0;
}