旅行商问题：城市间距离已知，求最短路径

这是一个典型的旅行商问题，可以使用动态规划求解。

设dp[i][S]表示从城市1出发，经过集合S中的所有城市，最终到达城市i的最短路径长度。其中集合S用二进制表示，第j位为1表示集合S中包含城市j。

初始状态为dp[1][1] = 0，其余为正无穷。

转移方程为：dp[i][S] = min{dp[j][S-{j}] + distance[i][j]}，其中j为集合S中的一个元素，distance[i][j]表示城市i到城市j的距离。

最终的答案为dp[10][2^10-1]，即从城市1出发，经过所有城市，最终到达城市10的最短路径长度。

最优路线中依次经过的城市顺序可以通过记录转移方程中的j值，反向推导出来。

代码实现如下：

const int N = 10;
const int INF = 0x3f3f3f3f;

int distance[N+1][N+1]; // distance[i][j]表示城市i到城市j的距离
int dp[N+1][1<<N]; // dp[i][S]表示从城市1出发，经过集合S中的所有城市，最终到达城市i的最短路径长度

int main()
{
    // 初始化distance数组
    memset(distance, INF, sizeof(distance));
    distance[1][2] = distance[2][1] = 20;
    distance[1][3] = distance[3][1] = 25;
    distance[1][4] = distance[4][1] = 37;
    distance[1][5] = distance[5][1] = 48;
    distance[1][6] = distance[6][1] = 40;
    distance[1][7] = distance[7][1] = 46;
    distance[1][8] = distance[8][1] = 71;
    distance[1][9] = distance[9][1] = 82;
    distance[2][3] = distance[3][2] = 28;
    distance[2][4] = distance[4][2] = 50;
    distance[2][5] = distance[5][2] = 18;
    distance[2][6] = distance[6][2] = 35;
    distance[2][7] = distance[7][2] = 35;
    distance[2][8] = distance[8][2] = 49;
    distance[2][9] = distance[9][2] = 64;
    distance[3][4] = distance[4][3] = 26;
    distance[3][5] = distance[5][3] = 37;
    distance[3][6] = distance[6][3] = 36;
    distance[3][7] = distance[7][3] = 23;
    distance[3][8] = distance[8][3] = 27;
    distance[3][9] = distance[9][3] = 53;
    distance[4][5] = distance[5][4] = 60;
    distance[4][6] = distance[6][4] = 52;
    distance[4][7] = distance[7][4] = 35;
    distance[4][8] = distance[8][4] = 25;
    distance[4][9] = distance[9][4] = 56;
    distance[5][6] = distance[6][5] = 26;
    distance[5][7] = distance[7][5] = 34;
    distance[5][8] = distance[8][5] = 51;
    distance[5][9] = distance[9][5] = 57;
    distance[6][7] = distance[7][6] = 18;
    distance[6][8] = distance[8][6] = 34;
    distance[6][9] = distance[9][6] = 30;
    distance[7][8] = distance[8][7] = 18;
    distance[7][9] = distance[9][7] = 31;
    distance[8][9] = distance[9][8] = 32;
    distance[9][10] = distance[10][9] = 40;

    // 初始化dp数组
    memset(dp, INF, sizeof(dp));
    dp[1][1] = 0;

    // 动态规划
    for (int S = 0; S < (1<<N); S++) {
        for (int i = 1; i <= N; i++) {
            if (!(S & (1<<(i-1)))) continue; // 集合S中不包含城市i
            for (int j = 1; j <= N; j++) {
                if (!(S & (1<<(j-1)))) continue; // 集合S中不包含城市j
                dp[i][S] = min(dp[i][S], dp[j][S^(1<<(i-1))] + distance[i][j]);
            }
        }
    }

    // 输出最短路径长度
    printf('%d
', dp[10][(1<<N)-1]);

    // 输出最优路线中依次经过的城市顺序
    int S = (1<<N)-1, i = 10;
    vector<int> path;
    while (S > 0) {
        for (int j = 1; j <= N; j++) {
            if (!(S & (1<<(j-1)))) continue; // 集合S中不包含城市j
            if (dp[i][S] == dp[j][S^(1<<(i-1))] + distance[i][j]) {
                path.push_back(j);
                S ^= (1<<(j-1));
                i = j;
                break;
            }
        }
    }
    reverse(path.begin(), path.end());
    printf('1 ');
    for (int i = 0; i < path.size(); i++) {
        printf('%d ', path[i]);
    }
    printf('10
');

    return 0;
}