【状压DP】最短Hamilton路径

题目

91. 最短Hamilton路径

---

给定一张 $n$ 个点的带权无向图，点从 $0 \sim n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短 Hamilton 路径。

Hamilton 路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$ 。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $a[i,j]$ ）。

对于任意的 $x,y,z$ ，数据保证 $a[x,x]=0，a[x,y]=a[y,x]$ 并且 $a[x,y]+a[y,z] \ge a[x,z]$ 。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

$1 \le n \le 20$
$0 \le a[i,j] \le 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

输出样例：

18

解题

方法一：贪心

思路

思维过程：

动态规划：

• 状态定义：$dp[i][j]$ 表示所有从顶点 $0$ 到顶点 $j$ ，走过的所有点状态为 $i$（状态压缩）的最短路径。
• 状态转移方程：$dp[i][j] = \min(dp[i - (1 <\!\!< j)][k] + g[j][k])$ （$k = 0 \dots n-1$） 。
• 初始状态：从顶点 $0$ 走到顶点 $0$ 只经过顶点 $0$ 的最短路径是：$dp[1_{(2)}][0]=0$

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int m = 1 << n;
        int[][] g = new int[n][n];
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                in.nextToken();
                g[i][j] = (int) in.nval;
            }
        }
        for (int i = 0; i < m; ++i) Arrays.fill(dp[i], INF);
        dp[1][0] = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i & (1 << j)) == 0) continue;
                for (int k = 0; k < n; ++k) {
                    if (((i - (1 << j)) & (1 << k)) == 0) continue;
                    dp[i][j] = Math.min(dp[i][j], dp[i - (1 << j)][k] + g[k][j]);
                }
            }
        }
        System.out.println(dp[m - 1][n - 1]);
    }
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 21, M = 1 << N;
int n, m;
int g[N][N];
int dp[M][N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) scanf("%d", &g[i][j]);
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    m = 1 << n;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                for (int k = 0; k < n; ++k) {
                    if ((i - (1 << j)) & (1 << k)) {
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + g[k][j]);
                    }
                }
            }
        }
    }
    printf("%d\n", dp[m - 1][n - 1]);
    
    return 0;
}