#include<cstdio>
#define INF 200000000
struct EDGE
{
	int st,ed,val;
}edge[1000000];
int dist[50002];
int n,result,max,min,nv;
bool inG[50002];
int getmin(int a,int b)
{
	if(a<b)
		return a;
	else
		return b;
}
int getmax(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}
void BellmanFord()
{
	int v,e,s=min;	
	for(v=min;v<max;v++)
	{
		dist[v]=-INF;
		edge[n].st=v;
		edge[n].ed=v+1;
		edge[n].val=0;
		n++;
		edge[n].st=v+1;
		edge[n].ed=v;
		edge[n].val=-1;
		n++;
	}	
	dist[s]=0;
	bool over=false;
	for(v=0;v<max-min&&!over;v++)
	{
		over=true;
		for(e=0;e<n;e++)
			if(dist[edge[e].st]!=-INF&&dist[edge[e].ed]<dist[edge[e].st]+edge[e].val)
			{
				dist[edge[e].ed]=dist[edge[e].st]+edge[e].val;
				over=false;
			}
	}	
	result=dist[max];
}	
int main()
{
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d%d%d",&edge[i].st,&edge[i].ed,&edge[i].val);
		edge[i].ed++;
		max=getmax(max,edge[i].ed);
		min=getmin(min,edge[i].st);
	}	
	BellmanFord();
	printf("%d\n",result);
	return 0;
}

• 个人建议:你把BELLMAN_FORD换成SPFA,顺便把小函数换成相应函数体的代码。。。 (1203) Luo_Luo 2011-08-25 10:27:11
  • Re:个人建议:你把BELLMAN_FORD换成SPFA,顺便把小函数换成相应函数体的代码。。。 (10) shllhsno1 2012-09-18 15:21:05