题目描述

小明目前在做一份毕业旅行的规划。

打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。

由于经费有限，希望能够通过合理的路线安排尽可能的省些路上的花销。

给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

注意：北京为 1号城市。

输入格式
城市个数 n。

城市间的车票价钱 n行 n列的矩阵 m[n][n]。

输出格式
输出一个整数，表示最小车费花销。

数据范围1<n≤20,包括北京车票价格均不超过 1000元。

输入样例：

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

输出样例：

1
13

说明
共 4个城市，城市 1和城市 1的车费为 0，城市 1和城市 2之间的车费为 2，城市 1和城市 3之间的车费为 6，城市 1和城市 4之间的车费为 5，以此类推。
假设任意两个城市之间均有单程票可买，且价格均在 1000元以内，无需考虑极端情况。

解题思路

使用状态压缩dp，需要注意我们最后还需要走回1号城市。
闫式dp

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.*;
import java.util.*;

class Main{
    public static int N = 1 << 20,M = 30;
    public static int[] index = new int[N];
    public static int[][] dp = new int[N][M],g = new int[M][M];
    public static Scanner sc = new Scanner(System.in);

    public static int lowbit(int x){
        return (-x) & x;
    }

    public static void main(String[] args){
        int n = sc.nextInt();

        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                g[i][j] = sc.nextInt();

        for(int i = 1;i <= n;i++) index[1 << (i - 1)] = i;
        for(int s = 0;s < 1 << n;s++) Arrays.fill(dp[s],0x3f3f3f3f);
        dp[1][1] = 0;

        for(int s = 2;s < (1 << n);s++){
            for(int i = 1;i <= n;i++){
                if((s & (1 << (i - 1))) != 0){
                    for(int j = 1;j <= n;j ++){
                        dp[s][i] = Math.min(dp[s][i],dp[s - (1 << (i - 1))][j] + g[j][i]);
                    }

                }
            }
        }

        int res = 0x3f3f3f3f;
        for(int i = 2;i <= n;i++) res = Math.min(res,dp[(1<<n) - 1][i] + g[1][i]);
        System.out.println(res);
    }
}