AcWing 91. 最短Hamilton路径
原题链接
中等
作者:
hhu-菜菜
,
2021-05-20 14:23:45
,
所有人可见
,
阅读 226
import java.util.Scanner;
import java.util.Arrays;
public class Main{
private static final int N = 20,M = 1 << N;
private static int n;
private static int[][] w = new int[N][N];
private static int[][] dp = new int[M][N];
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
w[i][j] = reader.nextInt();
}
}
reader.close();
//初始状态在0号点,从0走到0,走过的所有的带你只有0点,也就是0位上是1,其余所有位是0
for(int i = 0;i < 1<<n;i++){//其余点初始化
Arrays.fill(dp[i],Integer.MAX_VALUE/2);
}
dp[1][0] = 0;//起点
//i,k代表所有的状态
for(int i = 0;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 - (1<<j) >> k & 1) == 1){
dp[i][j] = Math.min(dp[i][j],dp[i-(1<<j)][k]+w[k][j]);
}
}
}
}
}
System.out.println(dp[(1<<n)-1][n-1]);
}
}