题目描述

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

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

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

输入描述

站点数n和各站点之间的距离(均为整数)，如：

3 {站点数}

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

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

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

输出描述

最短路程的数值

用例1

输入

3
0 2 1
1 0 2
2 1 0

Copy

输出

3

Copy

用例2

输入

4
0 2 1 3
1 0 2 5
2 1 0 4
3 2 6 0

Copy

输出

8

很明显，数量级(1 < n < 10)，很小，可以用全排列穷举所有情况：

代码：

import java.util.*;
import java.io.*;

    public class Main{
        public static int[][] m;
        public static int minDistance=Integer.MAX_VALUE;
        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.valueOf(br.readLine());
            m=new int[n][n];
            for(int i=0;i<n;i++) m[i]=Arrays.stream(br.readLine().split(" ")).mapToInt(k->Integer.valueOf(k)).toArray();
            int[] a=new int[n];
            for(int i=0;i<n;i++) a[i]=i;
            dfs(a,0,new int[n]);
            System.out.println(minDistance);

        }
        public static void dfs(int[] a,int i,int[] path){
            if(i==a.length){
                minDistance=Math.min(minDistance,getDistance(path));
                return;
            }

            for(int k=i;k<a.length;k++){
                swap(a,i,k);
                path[i]=a[i];
                dfs(a,i+1,path);
                swap(a,i,k);
            }

        }
        public static int getDistance(int[] path){
            int n=path.length;
            int ans=m[path[n-1]][path[0]];
            for(int i=0;i<n-1;i++) ans+=m[path[i]][path[i+1]];
            return ans;
        }

        public static void swap(int[] a,int i,int j){
            int t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
}