算法1

(暴力枚举) $O(2^n * n^2)$

时间复杂度

对该题的理解，弱鸡的无病呻吟。高手莫笑~~~ p.s. 开学了，没多少时间搞喜欢的算法了。

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20, INF = 0x3f3f3f3f;
// 该数组的第一位维是一个从0到19位有效的数
int f[1 << N][N], w[N][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);
    // 第一维为1，即20位数的第0位的值为1。
    // 恰似你已经站在编号为0的起点处，为遍历n个点做好了准备。
    // 第二维为0，表示你将要到达的点的编号为0
    // f[1][0] = 0 表示编号0的点到它自己的距离为0
    f[1][0] = 0; 

    // 从编号为0的点开始枚举
    // i = 1 表示你已经站在了编号为0的点上。因为1的二进制数的第0位就是1
    // 这里利用二进制数的位数与该位中保存的值之间的映射关系。这与数组的
    // 的下标与数组的元素之间的映射异曲同工吧
    // 即编号为0的点已经被划入访问过的点的集合
    for(int i = 1; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            // 查看i的第j位的值，为1表示访问过编号为j的点
            // 即表示从点的编号为i到点的编号j的路径(s)
            if(i >> j & 1)  
               for(int k = 0; k < n; k++)
                   // 对i的第j位置反，表示没有通过编号为j的点
                   // 然后，查看i的第k位的值，为1表示访问过编号为k的点
                   // 即表示从点的编号为i到点的编号k的路径(s)，但是中间没用通过编号为j的点
                   if((i ^ 1 << j) >> k & 1) 
                      // 这公式，只要是人都很熟悉了
                      f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1];
    return 0;
}