侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【状压DP】最短Hamilton路径

GabrielxD
2022-11-30 / 0 评论 / 0 点赞 / 35 阅读 / 831 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

91. 最短Hamilton路径


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

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

输入格式

第一行输入整数 nn

接下来 nn 行每行 nn 个整数,其中第 ii 行第 jj 个整数表示点 iijj 的距离(记为 a[i,j]a[i,j] )。

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

输出格式

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

数据范围

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

解题

方法一:贪心

思路

思维过程:

image-20221130184531434

动态规划:

  • 状态定义:dp[i][j]dp[i][j] 表示所有从顶点 00 到顶点 jj ,走过的所有点状态为 ii(状态压缩)的最短路径。
  • 状态转移方程:dp[i][j]=min(dp[i(1< ⁣ ⁣<j)][k]+g[j][k])dp[i][j] = \min(dp[i - (1 <\!\!< j)][k] + g[j][k])k=0n1k = 0 \dots n-1) 。
  • 初始状态:从顶点 00 走到顶点 00 只经过顶点 00 的最短路径是:dp[1(2)][0]=0dp[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;
}
0

评论区