TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市。求所走的最短路程。 输入：输入n表示城市数量。 输出：旅行家所走的路径，路径长度。 数据规模和约定： （1） 输入n：7n12 （2） 随机生成城市之间道路长度c[i][j]：1c[i][j]20 c++

以下是一个C++程序，使用了动态规划算法求解TSP问题：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 12;
const int INF = 0x3f3f3f3f;

int n; // 城市数量
int c[MAXN][MAXN]; // 道路长度
int dp[1<<MAXN][MAXN]; // dp数组，dp[S][i]表示经过集合S中的点，以i为终点的最短路程

int main() {
    // 输入城市数量
    cin >> n;

    // 输入道路长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> c[i][j];
        }
    }

    // 初始化dp数组
    memset(dp, INF, sizeof(dp));
    for (int i = 0; i < n; i++) {
        dp[1<<i][i] = 0;
    }

    // 动态规划
    for (int S = 0; S < (1<<n); S++) {
        for (int i = 0; i < n; i++) {
            if (!(S & (1<<i))) continue;
            for (int j = 0; j < n; j++) {
                if (S & (1<<j)) continue;
                dp[S|(1<<j)][j] = min(dp[S|(1<<j)][j], dp[S][i] + c[i][j]);
            }
        }
    }

    // 找到最短路程
    int ans = INF, last;
    for (int i = 0; i < n; i++) {
        if (dp[(1<<n)-1][i] < ans) {
            ans = dp[(1<<n)-1][i];
            last = i;
        }
    }

    // 输出路径和最短路程
    cout << last << " ";
    int S = (1<<n)-1;
    for (int i = n-1; i >= 1; i--) {
        int j;
        for (j = 0; j < n; j++) {
            if ((S & (1<<j)) && dp[S][last] == dp[S^(1<<last)][j] + c[last][j]) {
                break;
            }
        }
        cout << j << " ";
        S ^= (1<<last);
        last = j;
    }
    cout << "\n" << ans << endl;

    return 0;
}

其中，dp数组的含义为：dp[S][i]表示经过集合S中的点，以i为终点的最短路程。初始状态为dp[1<<i][i]=0，表示只经过i一个城市的情况下，到达i城市的距离为0。

动态规划的转移方程为：dp[S|(1<<j)][j] = min(dp[S|(1<<j)][j], dp[S][i] + c[i][j])，表示在集合S中经过i城市到达j城市的距离加上从i到j的距离，与在集合S并上j城市直接到达j城市的距离取最小值。最后，遍历dp[(1<<n)-1]数组，找到最小值，即为最短路程。然后根据dp数组，倒推出路径。