C++【问题描述】某售货员要到若干城市去推销商品，各城市之间的距离为已知. 他要选定一条从驻地出发经过所有城市最后回到驻地的周游路线，使得总的路程最短. 【输入形式】第一行输入无向图的顶点个数及边数。第二行开始输入顶点之间的边的长度(顶点i 顶点j ij边长度） 【输出形式】最短路程值

以下是C++代码实现，使用了动态规划的思想：

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

const int N = 20, INF = 0x3f3f3f3f;

int n, m;
int dist[N][N], f[1 << N][N];

int main()
{
    cin >> n >> m;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < n; i++)
        dist[i][i] = 0;
    while (m--)
    {
        int a, b, w;
        cin >> a >> b >> w;
        dist[a][b] = dist[b][a] = w;
    }

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int S = 1; S < 1 << n; S++)
        for (int i = 0; i < n; i++)
            if (S >> i & 1)
                for (int j = 0; j < n; j++)
                    if (j != i && (S >> j & 1))
                        f[S][i] = min(f[S][i], f[S ^ 1 << i][j] + dist[j][i]);

    cout << f[(1 << n) - 1][0] << endl;
    return 0;
}

注意到这里用到了一个技巧，即将状态S用二进制数表示。比如1<<i就表示只包含第i个顶点的集合。S >> i & 1表示S中是否包含第i个顶点。S ^ 1<<i表示从S中删除第i个顶点。