最短Hamilton路径

最短Hamilton路径

题目描述

给定一张 n(n \leq 20)(n≤20) 个点的带权无向图，点从0 \sim n-10∼n−1标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入描述:

第一行一个整数n。
接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（一个不超过10^710
7
的正整数，记为a[i,j]）。
对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且a[x,y]+a[y,z] \geq a[x,z]a[x,y]+a[y,z]≥a[x,z]。

输出描述

一个整数，表示最短Hamiltn路径

思路：

首先先将输入用数组w[i][j]存入,表示i到j的距离。
然后我们可以考虑用一个n位二进制数表示该点是否被经过，若第i位为1则被经过反之未被经过。还要知道当前是位于哪个点。所以可以用一个数组f[i][j]（0<i<2^n,0=<j<n）表示点被经过的状态。二进制i对应于j表示目前处于j点i状态的最短路径。先将该数组的“起点”f[0][1]设为0，然后将其余值全部设为最大值0x3f。最终得到的结果是f[1<<n-1,n-1],即当前状态经过了所有点，而且到达了终点。用循环遍历数组f[i][j],在i（二进制）的j位为1的情况下用一个变量k来遍历i的所有点，即将i的j位（取反）赋值为0后遍历i的每一位，考虑这样的k，取（f[i][j],f[i^1<<j][k]+w[k][j]）的最小值，就能得到从k到j的最短路径。

完整代码：

#include<iostream>
#include<string.h>
#include<cmath>
using namespace std;
int w[21][21],n;
int f[1 <<20][20];
int Hamilton()
{
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    for (int i = 1; i < 1 << n; i++)
        for (int j = 0; j < n; j++)
            if (i >> j & 1)//若i的j位为1
                for (int k = 0; k < n; k++)
                    if ((i ^ 1 << j) >> k & 1)//先将i的j位取反再看k位是否为1
                        f[i][j] = min(f[i][j], f[i ^ 1 << j][k] + w[k][j]);//
    return f[(1 << n) - 1][n - 1];

}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> w[i][j];
        }
    }
    cout << Hamilton();
    return 0;
}