;struct name{int u,v,w;}e[50005];int dist[50005];int main(){int i,j,k,n,u,v,w,mx,mn,t;bool f;while(~scanf(“%d”,&n)){for(i=0,mx=0,mn=1<<30;i<n;i++){scanf(“%d%d%d”,&u,&v,&w);mx=max(v,mx);mn=min(u,mn);e[i].u=v;e[i].v=u-1;e[i].w=-w;}for(i=0;i<=mx;i++)dist[i]=0;f=1;while(f){f=0;for(i=0;i<n;i++){t=dist[e[i].u]+e[i].w;if(t<dist[e[i].v]){dist[e[i].v]=t;f=1;}}for(i=mn;i<=mx;i++){if(dist[i]>dist[i-1]+1){dist[i]=dist[i-1]+1;f=1;}}for(i=mn;i<=mx;i++){if(dist[i]<dist[i-1]){dist[i-1]=dist[i];f=1;}}}printf(“%d\n”,dist[mx]-dist[mn-1]);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
来说是非者，便是是非人。
