记录编号	487314	评测结果	AAAAAAAAAA
题目名称	售货员的难题	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2018-02-09 17:23:59	内存使用	56.20 MiB

#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int d[20][20];
int f[1<<20][20];

const int INF = 1e9;

bool isIn(int x, int i) {
    i--;
    return (x & (1 << i) ) > 0;
}

int add(int x, int i) {
    i--;
    return x | (1 << i);
}

int main() {
    freopen("salesman.in", "r", stdin);
    freopen("salesman.out", "w", stdout);

    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &d[i][j]);
        }
    }

    for (int i = 0; i < (1 << N); i++) {
        for (int j = 1; j <= N; j++) {
            f[i][j] = INF;
        }
    }

    f[1][1] = 0;
    for (int i = 1; i < (1 << N); i++) {
        for (int j = 1; j <= N; j++) {
            if (f[i][j] >= INF) continue;

            for (int k = 1; k <= N; k++) {
                if (isIn(i, k)) continue;
                int ni = add(i, k);
                f[ni][k] = min(f[ni][k], f[i][j] + d[j][k]);
            }
        }
    }

    int ans = INF;
    for (int i = 2; i <= N; i++) {
        ans = min(ans, f[(1<<N) - 1][i] + d[i][1]);
    }
    printf("%d\n", ans);
    return 0;
}