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;
42 PriorityQueue<State> queue = new PriorityQueue<State>();
43
44 for(;;)
45 {
46 int n = sc.nextInt();
47 if( n==0 ) break;
48
49
50
51 n += 2;
52 int xs[] = new int[n];
53 int ys[] = new int[n];
54 int penalties[] = new int[n];
55
56
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
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 }