pku1201.cpp

内有pku1201

///POJ1201 Intervals 
//查分约束

#include <stdio.h>

const int INF = 1000000;
const int MAXE = 100000;
const int MAXV = 100000;
int st[MAXE], ed[MAXE], w[MAXE], V, E, min=INF, max=0;

int bellman_ford()
{
	int dis[MAXE], i, j;
	for(i=min; i<=max; i++){
		dis[i] = -INF;
	}
	dis[min] = 0;
	for(i=min; i<=max; i++){
		bool flag = true;
		for(j=0; j<E; j++){
			if(dis[ed[j]]<dis[st[j]]+w[j]){
				dis[ed[j]] = dis[st[j]] + w[j];
				flag = false;
			}
		}
		for(j=min; j<max; j++){
			if(dis[j+1]<dis[j]){
				dis[j+1] = dis[j];
				flag = false;
			}
		}
		for(j=max; j>min; j--){
			if(dis[j-1] < dis[j]-1){
				dis[j-1] = dis[j] - 1;
				flag = false;
			}
		}
		/*for(j=0; j<E; j++){
			if(dis[ed[j]]>dis[st[j]]+ed[j]-st[j]+1){
				dis[ed[j]] = dis[st[j]] + ed[j] -st[j] + 1;
				flag = false;
			}
		}*/
		if(flag) break;
	}
	return dis[max];
}

int main()
{
	int i, a, b, c;
	
	scanf("%d",&E);
	for(i=0; i<E; i++){	
		scanf("%d%d%d",&a, &b, &c);
		st[i] = a; ed[i] = b+1; w[i] = c;
		min = min<a?min:a; max = max>b+1?max:b+1;
	}
	printf("%d\n",bellman_ford());
	return 0;
}