(OD)基站维护工程师

目录

题目描述

输入描述

输出描述

代码

题目描述

              小王是一名基站维护工程师，负责某区域的基站维护。

              某地方有n 个基站（1<n<10），已知各基站之间的距离s（0<s<500），并且基站x 到基站y 的距离，与基站y 到基站x 的距离并不一定会相同。

              小王从基站1 出发，途径每个基站1 次，然后返回基站1，需要请你为他选择一条距离最短的路线。

输入描述

              站点数n 和各站点之间的距离（均为整数）。如：3 {站点数}

                            0 2 l {站点1 到各站点的路程}

                            1 0 2 {站点2 到各站点的路程}

                            2 1 0 {站点3 到各站点的路程}

输出描述

              最短路程的数值

分析：暂时能想到的方法就是全排列，给定一个 visited[] 数据标记已经走过的基站，出发时有 n - 1 个基站供选择，如图：

当走过一个后，还剩 n - 1 个基站未走

再走过一个后，还剩 n - 2 个基站未走

则 count（n） = distance（n） + count（n - 1）；则最后一次走法的可能性为1，倒数第二次走法的可能性为 1 * 2，倒数第三次走法的可能性为 1 * 2 * 3，用ArrayList存储当前基站此后的基站的走法的距离的可能性，向前递归

进行累加时，要用 visited 判断是否已经选择了

使用BufferedReader读取数据，提高效率

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class MaintenanceEngineer {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, int[]> map = new HashMap<>();
        int n = Integer.parseInt(in.readLine());
        for (int i = 0; i < n; i++) {
            String[] split = in.readLine().split(" ");
            int[] temp = new int[n];
            for (int j = 0; j < n; j++) {
                temp[j] = Integer.parseInt(split[j]);
            }
            map.put(i + 1, temp);
        }
        in.close();
        long start = System.currentTimeMillis();
        int[] visited = new int[n + 1];
        System.out.println(method(map, n, visited, 1));
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    public static int method(Map<Integer, int[]> map, int n, int[] visited, int index){
        int min = Integer.MAX_VALUE;
        for (int i = 2; i < n + 1; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                int int1 = map.get(index)[i - 1];
                ArrayList<Integer> count = count(map, n, visited, i);
                for (int item : count) {
                    min = Math.min(min, int1 + item);
                }
            }
        }
        return min;
    }
    public static ArrayList<Integer> count(Map<Integer, int[]> map, int n, int[] visited, int index){
        ArrayList<Integer> result = new ArrayList<>();
        int count = 0;
        boolean isAdd = true;
        for (int i = 2; i < n + 1; i++) {
            if (visited[i] == 0){
                isAdd = false;
                visited[i] = 1;
                ArrayList<Integer> count1 = count(map, n, visited, i);
                count += map.get(index)[i - 1];
                for (int item : count1){
                    result.add(item + count);
                }
            }
        }
        if (isAdd){
            result.add(map.get(index)[0]);
        }
        return result;
    }
}

经过测试，当 n 为10时，计算出最短距离耗时 1ms