2784642_ac_4059ms_5304k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main
{
	public static void main(String[] args)  throws Exception 
	{
		Scanner cin = new Scanner(System.in);
		
		int INF = 1000000;
		int n, i, j;
		int min, max;
		int u[] = new int [50001];
		int v[] = new int [50001];
		int w[] = new int [50001];
		boolean change;
		int dis[] = new int [50001];
	    
		n = cin.nextInt();
		max = -1;min =INF;
		for (i = 0; i < n; i++)
		{
			u[i] = cin.nextInt();
			v[i] = cin.nextInt();
			w[i] = cin.nextInt();
			v[i]++;
			if (u[i]<min)	min = u[i];
			if (v[i]>max)	max = v[i];
		}
		for (i = min; i <= max; i++)
			dis[i] = -INF;
		dis[min] = 0;
		change = true;
		for (i = min; i <= max&&change; i++)
		{
			change = false;
			for (j = 0; j < n; j++)
			{
				if(dis[u[j]]!=-INF&&dis[u[j]]+w[j]>dis[v[j]])
				{
					change = true;
					dis[v[j]] = dis[u[j]]+w[j];
				}
			}
			for (j = min+1; j <= max; j++)
		    {
				if(dis[j]<dis[j-1] && dis[j]!= -INF)
		        {
		            dis[j]=dis[j-1];
		            change = true;
		        }
		    }
			for(j = max; j > min; j--)
		    {
				if(dis[j]!= -INF && dis[j]-1>dis[j-1])
		        {
		            dis[j-1]=dis[j]-1;
		            change = true;
		        }
			}
		}
		System.out.println(dis[max]);
	}

}