题解 | #毕业旅行问题#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        int min = minTsp(map, n);
        System.out.println(min);
    }

    // drd notes: 城市不大于20个, 故可以用int的低20位来保存状态！
    public static int minTsp(int[][] map, int n) {
        int stateCount = (int) Math.pow(2, n - 1);
        int[][] dp = new int[n][stateCount];
        map[0][0] = Integer.MAX_VALUE;
        for (int city = 0; city < n; city++) {
            dp[city][0] = map[city][0];
        }
        for (int state = 1; state < stateCount; state++) {
            for (int city = 0; city < n; city++) {
                // 从city出发，经过state状态的城市集合，最终到达0城市，最小花费dp[city][state]
                dp[city][state] = Integer.MAX_VALUE;
                // 假如state包含城市city，不应该存在这种情况，故默认最大值即可
                if (city != 0 && hasVisited(state, city)) {
                    continue;
                }
                // 比如city包含4个城市，就拆为4个小问题，每个小问题包含3个城市
                for (int subCity = 1; subCity < n; subCity++) {
                    if (hasVisited(state, subCity)) {
                        int subState = 1 << (subCity - 1);
                        // 排除cityId后state
                        subState ^= state;
                        dp[city][state] = Math.min(dp[city][state], map[city][subCity] + dp[subCity][subState]);
                    }
                }
            }
        }
        return dp[0][dp[0].length - 1];
    }

    private static boolean hasVisited(int cities, int city) {
        return (cities >> city - 1 & 1) == 1;
    }
}