AcWing 91. 最短Hamilton路径
原题链接
中等
作者:
gongjin
,
2023-02-14 16:49:49
,
所有人可见
,
阅读 114
Java实现
import java.util.Arrays;
import java.util.Scanner;
class Main {
static int N = 20;
static int M = 1 << 20;
static int[][] f = new int[M][N];
static int[][] w = new int[N][N];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
w[i][j] = scanner.nextInt();
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
f[i][j] = (int) 1e8;
}
}
f[1][0] = 0;
for (int i = 0; i < 1 << n; i++) { //表示一种方案数
for (int j = 1; j < n; j++) { //表示路过了那个点
if ((i >> j & 1) == 1) { //验证是不是真的走到了这个点
for (int k = 0; k < n; k++) {
if (((i - (1 << j)) & 1) == 1) { //验证是不是走过了k这个点,并且k的路径中不包含j
f[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
}
}
}
}
System.out.println(f[(1 << n) - 1][n - 1]);
}
}