zoj 1508 Intervals 差分限制系統

題目大意：輸入n個區間，每個區間有3個值，ai，bi，ci代表在區間[ai,bi]上至少要有ci個整數點，現在要滿足所有區間的自身條件，問最少選多少個點。

類似zoj 2770可以模組化成一個差分限制系統.

#include <stdio.h>
#include <string.h>
int n,dist[50010];
struct e
{
	int u,v,w;
}edges[50010];
int mn,mx;
bool bellman()
{
	int i,t;
	int f=1;
	while(f)
	{
		f=0;
		for(i=0;i<n;i++)
		{
			t=dist[edges[i].u]+edges[i].w;
			if(dist[edges[i].v]>t)
			{
				dist[edges[i].v]=t;
				f=1;
			}
		}
		for(i=mn;i<=mx;i++)
		{
			t=dist[i-1]+1;
			if(dist[i]>t)
			{
				dist[i]=t;
				f=1;
			}
		}
		for(i=mx;i>=mn;i--)
		{
			t=dist[i];
			if(dist[i-1]>t)
			{
				dist[i-1]=t;
				f=1;
			}
		}
	}
	return true;
}

int main()
{
	int i,u,v,w;
	while(scanf("%d",&n)!=EOF)
	{
		memset(dist,0,sizeof(dist));
		mx=1;
		mn=99999;
		for(i=0;i<n;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			edges[i].u=v;
			edges[i].v=u-1;
			edges[i].w=-w;
			if(mn>u)
				mn=u;
			if(mx<v)
				mx=v;
		}
		bellman();
		printf("%d
",dist[mx]-dist[mn-1]);
	}
	return 0;
}