#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _node
{
	int a,quan;
	struct _node* next;
}node;
node *next[60000];
int d[60000];
void insert(int,int,int);
void SPFA();
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
	int i,j,n;
    int a,b,c;
    scanf("%d",&n);
    insert(0,1,1);
    for(i=1;i<55000;i++)
    {
		insert(i,i-1,0);
		insert(i,i+1,1);
	}
	for(i=0;i<n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		insert(b+1,a,-c);
	}
	SPFA();
	printf("%d\n",-d[0]);
    return 0;
}
void insert(int i,int a,int quan)
{
	node *tmp=next[i];
	next[i]=new node;
	next[i]->a=a;
	next[i]->quan=quan;
	next[i]->next=tmp;
}
void SPFA()
{
	int queue[60000]={44999},head=0,tail=1;
	int inqueue[60000],i,j;
	node *p;
	memset(inqueue,0,sizeof(inqueue));
	memset(d,127,sizeof(d));
	d[44999]=0;
	while(head!=tail)
	{
		i=queue[head++];
		head%=60000;
		inqueue[i]=0;
		p=next[i];
		while(p)
		{
			if(d[i]+p->quan<d[p->a])
			{
				d[p->a]=d[i]+p->quan;
				if(inqueue[p->a]==0)
				{
					queue[tail++]=p->a;
					tail%=60000;
					inqueue[p->a]=1;
				}
			}
			p=p->next;
		}
	}
}

• Re:求教：这道题有什么trick吗，WA数次，和同学的AC程序拍了很久没发现问题 (17) xyf 2010-06-23 11:34:25