Aizu Online Judge 0155 Spider Jin

■0155 Spider Jin

最初にどのビルからどのビルへ移動することが出来るかの辺を張る．あとはDijkstraをしながら，あるビルの前に訪れるビルを逐一記録しておけば良い．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  int[] b, x, y;  
18.  int m;  
19.  int[] s, g;  
20.  HashMap<Integer, Integer> map;  
21.   
22.  void run(){  
23.   for(;;){  
24.    n=sc.nextInt();  
25.    if(n==0){  
26.     break;  
27.    }  
28.    b=new int[n];  
29.    x=new int[n];  
30.    y=new int[n];  
31.    for(int i=0; i<n; i++){  
32.     b[i]=sc.nextInt();  
33.     x[i]=sc.nextInt();  
34.     y[i]=sc.nextInt();  
35.    }  
36.    m=sc.nextInt();  
37.    s=new int[m];  
38.    g=new int[m];  
39.    for(int i=0; i<m; i++){  
40.     s[i]=sc.nextInt();  
41.     g[i]=sc.nextInt();  
42.    }  
43.    solve();  
44.   }  
45.  }  
46.   
47.  void solve(){  
48.   map=new HashMap<Integer, Integer>();  
49.   for(int i=0; i<n; i++){  
50.    map.put(b[i], i);  
51.   }  
52.   
53.   @SuppressWarnings("unchecked")  
54.   LinkedList<E>[] es=new LinkedList[n];  
55.   for(int j=0; j<n; j++){  
56.    es[j]=new LinkedList<E>();  
57.    for(int i=0; i<n; i++){  
58.     if(i==j){  
59.      continue;  
60.     }  
61.     double cost=Math.hypot(x[i]-x[j], y[i]-y[j]);  
62.     if(cost<50+EPS){  
63.      es[j].add(new E(i, cost));  
64.     }  
65.    }  
66.   }  
67.   for(int i=0; i<m; i++){  
68.    LinkedList<Integer> path=dijkstra(es, map.get(s[i]), map.get(g[i]));  
69.    if(path==null){  
70.     println("NA");  
71.    }else{  
72.     for(int k=0; k<path.size(); k++){  
73.      print(b[path.get(k)]+(k==path.size()-1?"\n":" "));  
74.     }  
75.    }  
76.   }  
77.  }  
78.   
79.  LinkedList<Integer> dijkstra(LinkedList<E>[] es, int s, int g){  
80.   int n=es.length;  
81.   double[] d=new double[n];  
82.   int[] pre=new int[n];  
83.   PriorityQueue<P> que=new PriorityQueue<P>();  
84.   
85.   Arrays.fill(d, INF);  
86.   Arrays.fill(pre, -1);  
87.   d[s]=0;  
88.   pre[s]=s;  
89.   que.offer(new P(s, 0));  
90.   for(; !que.isEmpty();){  
91.    P p=que.poll();  
92.    if(d[p.v]<p.d)  
93.     continue;  
94.    for(E e : es[p.v]){  
95.     if(d[e.to]>d[p.v]+e.cost){  
96.      pre[e.to]=p.v;  
97.      d[e.to]=d[p.v]+e.cost;  
98.      que.offer(new P(e.to, d[e.to]));  
99.     }  
100.    }  
101.   }  
102.   LinkedList<Integer> path=new LinkedList<Integer>();  
103.   for(int i=g;; i=pre[i]){  
104.    path.addFirst(i);  
105.    if(i==-1){  
106.     return null;  
107.    }  
108.    if(i==s){  
109.     return path;  
110.    }  
111.   }  
112.  }  
113.   
114.  class E{  
115.   int to;  
116.   double cost;  
117.   
118.   E(int to, double cost){  
119.    this.to=to;  
120.    this.cost=cost;  
121.   }  
122.  }  
123.   
124.  class P implements Comparable<P>{  
125.   int v;  
126.   double d;  
127.   
128.   P(int v, double d){  
129.    this.v=v;  
130.    this.d=d;  
131.   }  
132.   
133.   @Override  
134.   public int compareTo(P p){  
135.    if(d+EPS<p.d){  
136.     return -1;  
137.    }else if(d>p.d+EPS){  
138.     return 1;  
139.    }else{  
140.     return 0;  
141.    }  
142.   }  
143.  }  
144.   
145.  void debug(Object... os){  
146.   System.err.println(Arrays.deepToString(os));  
147.  }  
148.   
149.  void print(String s){  
150.   System.out.print(s);  
151.  }  
152.   
153.  void println(String s){  
154.   System.out.println(s);  
155.  }  
156.   
157.  public static void main(String[] args){  
158.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
159.   new Main().run();  
160.  }  
161. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] b, x, y;
 int m;
 int[] s, g;
 HashMap<Integer, Integer> map;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   b=new int[n];
   x=new int[n];
   y=new int[n];
   for(int i=0; i<n; i++){
    b[i]=sc.nextInt();
    x[i]=sc.nextInt();
    y[i]=sc.nextInt();
   }
   m=sc.nextInt();
   s=new int[m];
   g=new int[m];
   for(int i=0; i<m; i++){
    s[i]=sc.nextInt();
    g[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  map=new HashMap<Integer, Integer>();
  for(int i=0; i<n; i++){
   map.put(b[i], i);
  }

  @SuppressWarnings("unchecked")
  LinkedList<E>[] es=new LinkedList[n];
  for(int j=0; j<n; j++){
   es[j]=new LinkedList<E>();
   for(int i=0; i<n; i++){
    if(i==j){
     continue;
    }
    double cost=Math.hypot(x[i]-x[j], y[i]-y[j]);
    if(cost<50+EPS){
     es[j].add(new E(i, cost));
    }
   }
  }
  for(int i=0; i<m; i++){
   LinkedList<Integer> path=dijkstra(es, map.get(s[i]), map.get(g[i]));
   if(path==null){
    println("NA");
   }else{
    for(int k=0; k<path.size(); k++){
     print(b[path.get(k)]+(k==path.size()-1?"\n":" "));
    }
   }
  }
 }

 LinkedList<Integer> dijkstra(LinkedList<E>[] es, int s, int g){
  int n=es.length;
  double[] d=new double[n];
  int[] pre=new int[n];
  PriorityQueue<P> que=new PriorityQueue<P>();

  Arrays.fill(d, INF);
  Arrays.fill(pre, -1);
  d[s]=0;
  pre[s]=s;
  que.offer(new P(s, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v]<p.d)
    continue;
   for(E e : es[p.v]){
    if(d[e.to]>d[p.v]+e.cost){
     pre[e.to]=p.v;
     d[e.to]=d[p.v]+e.cost;
     que.offer(new P(e.to, d[e.to]));
    }
   }
  }
  LinkedList<Integer> path=new LinkedList<Integer>();
  for(int i=g;; i=pre[i]){
   path.addFirst(i);
   if(i==-1){
    return null;
   }
   if(i==s){
    return path;
   }
  }
 }

 class E{
  int to;
  double cost;

  E(int to, double cost){
   this.to=to;
   this.cost=cost;
  }
 }

 class P implements Comparable<P>{
  int v;
  double d;

  P(int v, double d){
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   if(d+EPS<p.d){
    return -1;
   }else if(d>p.d+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}