题目描述

给定一张 n
个点的带权无向图，点从 0∼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]≥a[x,z]
。

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

数据范围
1≤n≤20

0≤a[i,j]≤107

样例

输入样例：
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

本题要求算出经过每个点，距离加起来最小，
可以通过二进制运算
如何表示呢？
以13这个数为例，它的二进制表示为1101，自右往左看，可以看作为1011，表示为1这个点包含，2这个点没包含，3和4这个点包含。
带入题目f[i][j], 其中i看作二进制表示依次进行着类似i>>j的运算，计算通过i这种路径到j这个点经过的距离。
ok,上代码

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 21, M = 1 << N;

int w[N][N];
int f[M][N];
int n;

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

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1) //i中要包含j才可以
                for (int k = 0; k < n; k ++ )   
                    if ((i - (1 << j)) >> k & 1) //i去除j后有k
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);

    cout << f[(1 << n) - 1][n - 1];
}