最短Hamilton路径 给定一张 nn 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式 第一行输入整数n。
接下来n行每行n个整数，其中第i行第j个整数表示点ii到jj的距离（记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
输出格式 输出一个整数，表示最短Hamilton路径的长度。
数据范围 1≤n≤20 0≤a[i,j]≤10^7
输入样例： 5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0 1 2 3 4 5 6 输出样例： 18
import java.util.Scanner; //该题目使用枚举全排列的方法复杂度达到了n!。因此采用状态压缩降低复杂度 //用二进制位来表示选取了哪些点，选取的点为1，不选取的点为0 //dp[i][j]来表示 在遍历到第i种排列情况时，当前状态为j的最短路径。 // 首先要遍历所有可能的路径状态，转换成二进制的排布--i。在遍历到排列状况为i的情况时，所有为1的位置都有可能是刚刚遍历到的位置，称为当前状态。 // 例如，111011 5个1都有可能是最新遍历到的位置。因此需要再次遍历所有为1的位置，以求出在i的排布情况下，没种状态下的最优路径。 //在遍历当前状态的情况下，目标是找出最短路径。当前状态的最短路径是和上一次的状态是有关系的。 // 在排布为111011的情况下，每一个1都可能是当前状态，除掉当前状态的1 其余的所有1都有可能的上一次的状态，因此需要遍历每一种可能的上一状态求出当前状态的最优路径。 //综上所述 需要三层遍历 状态转移方程为 dp[i][j] = Math.min(dp[i][j], dp[i^(1<<j)][k] + a[k][j]); //公式中第二项的意思为： i^(1<<j)这一部分是把当前状态j置0 以保证上一状态不会提前遍历到这个位置，k项是遍历出所有可能的上一状态 然后再加上a[k][j] 当前状态与上一状态的距离。 class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] a = new int[n][n]; for (int i = 0;i<n;++i){ for (int j = 0;j<n;++j){ a[i][j] = sc.nextInt(); } } int[][] dp = new int[1<<n][n]; for (int i=0;i<(1<<n);++i){ for (int j=0;j<n;++j){ dp[i][j] = 111111111; } } dp[1][0]=0;//只有一个点 还没走 当然走了0 //for (int i = 0;i<1<<n;++i){ for (int i = 1;i<(1<<n);++i){ for (int j=0;j<n;++j){ if (((i>>j)&1)==1){ for (int k =0;k<n;++k){ if (((i>>k)&1)==1){ // dp[i][j] = Math.min(dp[i][j],dp[i^(1<<k)][j]+a[i^(1<<k)][k]); dp[i][j] = Math.min(dp[i][j], dp[i^(1<<j)][k] + a[k][j]); } } } } } System.out.println(dp[(1<<n)-1][n-1]); } }