#include<cstdio>
#include<iostream>
using namespace std;

int n,m,s;
int E[100200][3];
int D[50100];

void BellmanFord(){
	int i,j,k;
	for(i=s;i<=m;i++)D[i]=1;
	D[s]=0;
	for(k=1;k<=m;k++){
		
		for(j=0;j<n;j++){
			int u=E[j][0],v=E[j][1],e=E[j][2];
			if(D[u]!=1&&D[v]>D[u]+e){
				D[v]=D[u]+e;
			}
		}
		
	}
	
	printf("%d\n",-D[m]);
}

int main(){
	//freopen("in.txt","r",stdin);
	scanf("%d",&n);
	int i;
	int u,v,e;
	m=-1;s=-1;
	
	for(i=0;i<n;i++){
		scanf("%d%d%d",&u,&v,&e);
		E[i][0]=u;
		if(s==-1||s>u)s=u;
		E[i][1]=v+1;
		if(v+1>m)m=v+1;
		E[i][2]=-e;
	}
	
	for(i=s;i<m;i++){
		E[n][0]=i;
		E[n][1]=i+1;
		E[n][2]=0;
		n++;
	}
	
	BellmanFord();
	
}

• 最长路是NP的。。。 (815) e_at_fdu 2005-10-19 17:20:31
• 在这里AC的代码在ZOJ上提交就WA了！sign~~ (0) animate 2005-10-19 19:47:35
  • 输入要改一下吧，那边一般都是多case的 (0) frkstyc 2005-10-19 19:48:26