acwing-91. 最短Hamilton路径

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
41
42
43
44
45
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] weight = new int[n][n];
        
        // 写入数据
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                weight[i][j] = sc.nextInt();
            }
        }
        
        System.out.println(hamilton(n, weight));
    }
    
    public static int hamilton(int n, int[][] weight){
        
        // 定义点到点的边距
        int[][] dist = new int[1<<n][n];
        // 初始化边距
        for(int i = 0; i < (1 << n); i++){
            Arrays.fill(dist[i], Integer.MAX_VALUE >> 1);
        }
        // 还没出发则为0
        dist[1][0] = 0;
        
        for(int i = 0; i < (1 << n); i++){
            for(int j = 0; j < n; j++){
                // 到达j这个点的最短距离
                if((i>>j & 1) == 1){
                    for(int k = 0; k < n; k++){
                        // 从k这个点走到j这个点
                        if ((i >> k & 1) == 1){
                            dist[i][j] = Math.min(dist[i][j], dist[i-(1<<j)][k] + weight[k][j]);
                        }
                    }
                }
            }
        }
        
        return dist[(1<<n) - 1][n-1];
    }
}