The Java Program: H_robot/robotchallenge_dijkstra.java

  1 import java.io.*;
  2 import java.util.*;
  3 import java.awt.*;
  4 import java.awt.geom.*;
  5 import java.text.*;
  6 import java.math.*;
  7 
  8 class robotchallenge_dijkstra
  9 {
 10     public Scanner sc;
 11     public PrintStream ps;
 12 
 13     public String toString()
 14     {
 15         return "robotchallenge_dijkstra";
 16     }
 17     
 18     public class State implements Comparable<State>
 19     {
 20         public int node;
 21         public double cost;
 22         
 23         public State( int n, double c )
 24         {
 25                 node = n;
 26                 cost = c;
 27         }
 28         
 29         public int compareTo( State s )
 30         {
 31                 int result = Double.compare( cost, s.cost );
 32                 if( result==0 ) result = s.node - node;
 33                 
 34                 return result;
 35         }
 36     }
 37 
 38     public void doit() throws Exception
 39     {
 40         sc = new Scanner( new File( "robotchallenge.judge" ) );
 41         ps = System.out; //new PrintStream( new FileOutputStream( "robotchallenge.out" ) ); //System.out;
 42         PriorityQueue<State> queue = new PriorityQueue<State>();
 43                 
 44         for(;;)
 45         {
 46             int n = sc.nextInt();
 47             if( n==0 ) break;
 48 
 49             // We're going to add 2 points to the input.
 50             // The start (0,0) and the end (100,100)
 51             n += 2;
 52             int xs[] = new int[n];
 53             int ys[] = new int[n];
 54             int penalties[] = new int[n];
 55 
 56             // The start will be the first point, with a practically infinite penalty
 57             xs[0] = 0;
 58             ys[0] = 0;
 59             penalties[0] = 1000000000;
 60 
 61             for( int i=1; i<n-1; i++ )
 62             {
 63                 xs[i] = sc.nextInt();
 64                 ys[i] = sc.nextInt();
 65                 penalties[i] = sc.nextInt();
 66             }
 67             
 68             // The end will be the last point, with a practically infinite penalty
 69             xs[n-1] = 100;
 70             ys[n-1] = 100;
 71             penalties[n-1] = 100000000;
 72             
 73             queue.clear();
 74             boolean visited[] = new boolean[n];
 75             Arrays.fill( visited, false );
 76             double answer = 0.0;
 77             
 78             queue.add( new State( 0, 0.0 )  );
 79             while( queue.size()>0 )
 80             {
 81                 State s = queue.poll();
 82                 if( !visited[s.node] )
 83                 {
 84                         visited[s.node] = true;
 85                         if( s.node==n-1 )
 86                         {
 87                             answer = s.cost;
 88                             break;
 89                         }
 90                         
 91                         double penalty = 0.0;
 92                         for( int i=s.node+1; i<n; i++ ) 
 93                     {
 94                                 if( !visited[i] )
 95                                 {
 96                                         int dx = xs[i]-xs[s.node];
 97                                         int dy = ys[i]-ys[s.node];
 98                                         double dist = Math.sqrt( dx*dx + dy*dy );
 99                                         double cost = s.cost + dist + penalty + 1.0;
100                                         queue.add( new State( i, cost )  );
101                                 }
102                                 penalty += penalties[i];
103                         }
104                 }
105             }
106             
107             ps.printf( "%.3f", answer );
108             ps.println();
109 
110         }
111     }
112     
113         public static void main(String[] args) throws Exception
114         {
115                 long starttime = System.currentTimeMillis();
116                 new robotchallenge_dijkstra().doit();
117                 System.out.println( System.currentTimeMillis() - starttime );
118         }
119 }