用c++实现n叉树旅行售货员问题

以下是一个简单的C++实现，该代码使用了深度优先搜索算法来解决旅行售货员问题，时间复杂度为O(n!)，其中n是城市的数量。

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n, ans = INT_MAX;
int g[N][N], vis[N];

void dfs(int u, int cnt, int dist) {
    if (cnt == n) {
        ans = min(ans, dist + g[u][1]);
        return;
    }
    for (int v = 2; v <= n; ++v) {
        if (vis[v]) continue;
        vis[v] = true;
        dfs(v, cnt + 1, dist + g[u][v]);
        vis[v] = false;
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> g[i][j];
        }
    }
    vis[1] = true;
    dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}

以上代码中，g[i][j]表示城市i到城市j的距离，vis数组用来记录某个城市是否被访问过，dfs函数表示深度优先搜索算法，其中u表示当前所在城市，cnt表示已经访问过的城市数量，dist表示已经走过的总路程。在dfs函数中，如果已经访问过所有城市，则更新答案，否则继续向下搜索。