fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Edge implements Comparable<Edge>{
  5.     int end;
  6.     int value;
  7.  
  8.     Edge(int end, int value) {
  9.         this.end = end;
  10.         this.value = value;
  11.     }
  12.     public int compareTo(Edge o) {
  13.         return this.value - o.value;
  14.     }
  15. }
  16.  
  17. public class Main {
  18.     public static void main(String[] args) throws IOException {
  19.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  20.         StringTokenizer st = new StringTokenizer(br.readLine());
  21.         int N = Integer.parseInt(st.nextToken());
  22.         int K = Integer.parseInt(st.nextToken());
  23.         int num = Math.max(N,K);
  24.  
  25.         ArrayList<Edge>[] list = new ArrayList[num*2+1];
  26.         int[] distance = new int[num*2+1];
  27.         boolean[] check = new boolean[num*2+1];
  28.  
  29.         for(int i = 0; i<=num*2; i++) {
  30.             list[i] = new ArrayList<>();
  31.         }
  32.         Arrays.fill(distance,Integer.MAX_VALUE);
  33.         list[0].add(new Edge(1,1));
  34.  
  35.         for(int i = 1; i<=num*2; i++) {
  36.             list[i].add(new Edge(i-1,1));
  37.             list[i].add(new Edge(i+1,1));
  38.             list[i].add(new Edge(i*2,1));
  39.         }
  40.  
  41.         distance[N] = 0;
  42.  
  43.         PriorityQueue<Edge> queue = new PriorityQueue<>();
  44.         queue.add(new Edge(N,0));
  45.         int[] route = new int[num+1];
  46.  
  47.         while(!queue.isEmpty()) {
  48.             Edge a = queue.poll();
  49.             if(check[a.end])
  50.                 continue;
  51.  
  52.             check[a.end] = true;
  53.             for(Edge o : list[a.end]) {
  54.                 if(o.end > num || o.end<0)
  55.                     continue;
  56.  
  57.                 if(distance[o.end] > distance[a.end] + o.value) {
  58.                     distance[o.end] = distance[a.end] + o.value;
  59.                     queue.add(new Edge(o.end, distance[o.end]));
  60.                     route[o.end] = a.end;
  61.                 }
  62.             }
  63.         }
  64.         System.out.println(distance[K]);
  65.  
  66.         int tmp = K;
  67.         Stack<Integer> stack = new Stack<>();
  68.         while(true) {
  69.             stack.push(tmp);
  70.             tmp = route[tmp];
  71.             if(tmp==0)
  72.                 break;
  73.         }
  74.         if(N!=K && N==0)
  75.             stack.push(0);
  76.  
  77.         while(!stack.isEmpty())
  78.             System.out.print(stack.pop() + " ");
  79.         System.out.println("");
  80.     }
  81. }
Success #stdin #stdout 0.12s 36028KB
comments (?)
stdin
copy 
4 7
stdout
copy 
3
4 3 6 7
https://ideone.com/xIJsKQ
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!