给定一张n个点的带权无向图,点从0n−1标号,求起点0到终点n−1的最短 Hamilton 路径。 Hamilton 路径的定义是从0n−1不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数n。 接下来n行每行n个整数,其中第i行第j个整数表示点ij的距离(记为a[i, j])。 对于任意的x, y, z,数据保证a[x, x]=0a[x, y]=a[y, x]并且a[x, y]+a[y, z]≥a[x, z]

输出格式

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

数据范围 1 ≤ n ≤ 20 0 ≤ a[i, j] ≤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

题目分析

可以先想到朴素做法DFS。在DFS过程中,我们会发现可以将状态压缩存储。提交 DFS 代码会TLE,所以我们考虑状态压缩DP。

代码实现

DFS(TLE)

#include <iostream>
using namespace std;
const int N = 30, INF = 0x7fffffff;

int n, g[N][N], ans = INF;
void dfs(int s, int st, int len) {
    if(s == n - 1 && st == (1 << n) - 1) {
        ans = min(ans, len);
        return ;
    }
    for(int i = 1; i < n; ++i) {
        if(i == s || st & (1 << i)) continue;
        else dfs(i, st + (1 << i), len + g[s][i]);
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) cin >> g[i][j];
    dfs(0, 1, 0);
    cout << ans;
    return 0;
}

DP

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << 20;

int n, g[N][N], dp[M][N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j) cin >> g[i][j];
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for(int i = 0; i < 1 << n; ++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]);
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1];
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status