题解 | #树上最短路#

用java答题有点吃亏。 以下代码运行超时：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int count = in.nextInt();
        int ret[] = new int[count];
        
        for (int i = 0; i < count; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int distanceStep = 0;


            while ((a - b) != 0) {

                if (a > b) {
                    a = a / 2;
                } else {
                    b = b / 2;
                }
                
                distanceStep++;
            }

            ret[i] = distanceStep;
            System.out.println(distanceStep);
            //System.out.println(ret[i]);
        }

        // for (int item : ret) {
        //     System.out.println(item);
        // }
        


        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
    }
}

以下代码运行通过：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int count = in.nextInt();
        int ret[] = new int[count];
        
        for (int i = 0; i < count; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int distanceStep = 0;


            while ((a - b) != 0) {

                if (a > b) {
                    a = a / 2;
                } else {
                    b = b / 2;
                }
                
                distanceStep++;
            }

            ret[i] = distanceStep;
            System.out.println(ret[i]);
        }

        // for (int item : ret) {
        //     System.out.println(item);
        // }
        


        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
    }
}

其实两种实现在算法上没有本质区别，只能说java语言封装了太多的东西，进而影响了程序运行的性能。