rally/rally_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to which is Greater?
  8  * 
  9  * @author vanb
 10  */
 11 public class rally_vanb
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15     
 16     public class Road
 17     {
 18         public int a, b;
 19         public int start, stop, time;
 20         
 21         public Road( int a, int b, int start, int stop, int time )
 22         {
 23             this.a = a;
 24             this.b = b;
 25             this.start = start;
 26             this.stop = stop;
 27             this.time = time;
 28         }
 29         
 30         public int other( int s )
 31         {
 32             return s==a ? b : a;
 33         }
 34         
 35         public String toString()
 36         {
 37             return "{" + a + "-" + b + ", " + start + ", " + stop + ", " + time + "}";
 38         }
 39     }
 40     
 41     public class State implements Comparable<State>
 42     {
 43         public int station;
 44         public int minutes;
 45         public int charge;
 46         
 47         public State( int s, int m, int c )
 48         {
 49             station = s;
 50             minutes = m;
 51             charge = c;
 52         }
 53         
 54         public int compareTo( State s )
 55         {
 56             return minutes - s.minutes;
 57         }
 58     }
 59         
 60     /**
 61      * Driver.
 62      * @throws Exception
 63      */
 64     public void doit() throws Exception
 65     {
 66         sc = new Scanner( new File( "rally.judge" ) );
 67         ps = new PrintStream( new FileOutputStream( "rally.vanb" ) );
 68         
 69         LinkedList<Road>[] stations = new LinkedList[500];
 70         for( int i=0; i<500; i++ )
 71         {
 72             stations[i] = new LinkedList<Road>();
 73         }
 74         
 75         int thresh[] = new int[500];
 76         
 77         PriorityQueue<State> pq = new PriorityQueue<State>();
 78 
 79         for(;;)
 80         {
 81             int n = sc.nextInt();
 82             int m = sc.nextInt();
 83             if( n==0 && m==0 ) break;
 84             
 85             for( int i=0; i<n; i++ )
 86             {
 87                 stations[i].clear();
 88             }
 89             
 90             for( int i=0; i<m; i++ )
 91             {
 92                 int a = sc.nextInt();
 93                 int b = sc.nextInt();
 94                 int start, stop, time;
 95                 do
 96                 {
 97                     start = sc.nextInt();
 98                     stop = sc.nextInt();
 99                     time = sc.nextInt();
100                     if( time<=240 )
101                     {
102                         Road road = new Road( a, b, start, stop, time );
103                         stations[a].add( road );
104                         stations[b].add( road );
105                     }
106                 } while( stop<1439 );
107             }
108             
109             Arrays.fill( thresh, Integer.MAX_VALUE );
110 
111             pq.clear();
112             pq.add( new State( 0, 0, 480 ) );
113             int best = 0;
114             while( !pq.isEmpty() )
115             {
116                 State s = pq.poll();
117                 //.err.println(  Reach station   + s.station +   after   + s.minutes );
118                 if( s.station==n-1 )
119                 {
120                     best = s.minutes;
121                     break;
122                 }
123                 
124                 if( s.minutes + 480 - s.charge <= thresh[s.station] )
125                 {
126                     thresh[s.station] = s.minutes + 480 - s.charge;
127 
128                     int currenttime = (s.minutes+720) % 1440;
129                     //System.err.println(  Current time   + currenttime );
130                     for( Road road : stations[s.station] )
131                     {
132                         //System.err.println(  Looking at road   + road );
133                         int t = road.other( s.station );
134                         //if( !visited[t] )
135                         //{
136                             int wait = 0;
137                             if( currenttime < road.start )
138                             {
139                                 wait = road.start - currenttime;
140                             }
141                             else if( currenttime > road.stop )
142                             {
143                                 wait = road.start - currenttime + 1440;                            
144                             }
145     
146                             int newcharge = Math.min( s.charge + wait, 480 );
147                             if( road.time*2 <= newcharge )
148                             {
149                                 pq.add( new State( t, s.minutes+wait+road.time, newcharge-road.time*2 ) );
150                             }
151                             else
152                             {
153                                 int need = road.time*2 - newcharge;
154                                 wait += need;
155                                 int depart = (currenttime + wait) % 1440;
156                                 if( depart < road.start )
157                                 {
158                                     wait += road.start - depart;
159                                 }
160                                 else if( depart > road.stop )
161                                 {
162                                     wait += road.start - depart + 1440;                            
163                                 }
164      
165                                 newcharge = Math.min( s.charge + wait, 480 );
166                                 pq.add( new State( t, s.minutes+wait+road.time, newcharge-road.time*2 ) );
167                             }
168                        // }
169                     }
170                 }
171             }
172             
173             ps.println( best );
174             
175         }
176     }
177     
178     /**
179      * @param args
180      */
181     public static void main( String[] args ) throws Exception
182     {
183         new rally_vanb().doit();        
184     }   
185 }