Source Code

Problem: 2374  User: yzhw 
Memory: 45284K  Time: 5907MS 
Language: Java  Result: Accepted 

Source Code 
import java.io.*;
import java.util.*;
class stnode
{
	int s,e;
	boolean cover=false;
	int covernum=-2;
}
class st
{
	stnode data[]=new stnode[1000000];
	st()
	{
	   for(int i=0;i<1000000;i++)
		   data[i]=new stnode();
	   make(0,200001,1);
	}
	void make(int s,int e,int pos)
	{
	   data[pos].s=s;
	   data[pos].e=e;
	   if(e!=s+1)
	   {
		   make(s,(s+e)/2,pos*2);
		   make((s+e)/2,e,pos*2+1);
	   }
	}
	int get(int pos)
	{
		return get(pos+100000,pos+100001,1);
	}
	int get(int s,int e,int pos)
	{
		if(data[pos].covernum>=0)
			return data[pos].covernum;
		int mid=(data[pos].s+data[pos].e)/2;
		if(e<=mid)
			return get(s,e,pos*2);
		else
			return get(s,e,pos*2+1);
	}
	void insert(int s,int e,int num)
	{
		insert(s+100000,e+100001,num,1);
	}
	void insert(int s,int e,int num,int pos)
	{
	    if(data[pos].s==s&&data[pos].e==e)
	    {
	       data[pos].cover=true;
	       data[pos].covernum=num;
	    }
	    else
	    {
	       if(data[pos].cover)
	       {
	    	   data[pos*2].cover=data[pos*2+1].cover=true;
	    	   data[pos*2].covernum=data[pos*2+1].covernum=data[pos].covernum;
	    	   data[pos].cover=false;
	       }
	       int mid=(data[pos].s+data[pos].e)/2;
	       if(e<=mid)
	    	   insert(s,e,num,pos*2);
	       else if(s>=mid)
	    	   insert(s,e,num,pos*2+1);
	       else
	       {
	    	   insert(s,mid,num,pos*2);
	    	   insert(mid,e,num,pos*2+1);
	       }
	       if(data[pos*2].covernum==data[pos*2+1].covernum)
	    	   data[pos].covernum=data[pos*2].covernum;
	       else
	    	   data[pos].covernum=-1;
	    }
	}
}
class node
{
   int next,val;
   node(int a,int b)
   {
	   next=a;
	   val=b;
   }
}
public class Main {
	static ArrayList <node>g[];
	//static LinkedList<Integer> q=new LinkedList<Integer>();
	static int data[][];
	static int len[];
	static int q[]=new int[150000],s=-1,e=-1;
	static boolean used[]=new boolean[150000];
	static boolean empty()
	{
		return s==e&&s!=-1;
	}
	static void push(int pos)
	{
		e=(e+1)%150000;
		q[e]=pos;
	}
	static int pull()
	{
		s=(s+1)%150000;
		return q[s];
	}
	public static void main(String[] args) throws IOException{
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		int s,n;
		st set=new st();
		in.nextToken();
		n=(int)in.nval;
		in.nextToken();
		s=(int)in.nval;
		data=new int[n+1][2];
		g=new ArrayList[2*(n+1)];
		for(int i=0;i<2*(n+1);i++)
			g[i]=new ArrayList<node>();
		set.insert(-100000, 100000, 0);
		for(int i=1;i<=n;i++)
		{
			in.nextToken();
			data[i][0]=(int)in.nval;
			in.nextToken();
			data[i][1]=(int)in.nval;
			int aa=set.get(data[i][0]),bb=set.get(data[i][1]);
		//	System.out.println(i+" "+aa+" "+bb);
			if(aa==0)
				g[i*2-1].add(new node(0,Math.abs(data[i][0])));
			else
			{
				g[i*2-1].add(new node(2*aa-1,Math.abs(data[i][0]-data[aa][0])));
				g[i*2-1].add(new node(2*aa,Math.abs(data[i][0]-data[aa][1])));
			}
			if(bb==0)
				g[i*2].add(new node(0,Math.abs(data[i][1])));
			else
			{
				g[i*2].add(new node(2*bb-1,Math.abs(data[i][1]-data[bb][0])));
				g[i*2].add(new node(2*bb,Math.abs(data[i][1]-data[bb][1])));
			}	
			set.insert(data[i][0],data[i][1],i);
		}
		g[2*n+1].add(new node(2*n-1,Math.abs(s-data[n][0])));
		g[2*n+1].add(new node(2*n,Math.abs(s-data[n][1])));
		len=new int[2*n+2];
		Arrays.fill(len, 0xfffffff);
		len[2*n+1]=0;
		push(2*n+1);
		Arrays.fill(used, false);
		used[2*n+1]=true;
		while(!empty())
		{
			int top=pull();
			used[top]=false;
			for(int i=0;i<g[top].size();i++)
			{
				if(len[g[top].get(i).next]>len[top]+g[top].get(i).val)
				{
					len[g[top].get(i).next]=len[top]+g[top].get(i).val;
					if(!used[g[top].get(i).next])
						push(g[top].get(i).next);
					used[g[top].get(i).next]=true;
				}
			}
		}
		System.out.println(len[0]);
	}

}

• советую (0) besplatno 2012-03-05 15:57:50