> #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;
> }

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