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

根据题目描述，这是一个 TSP（Traveling Salesman Problem）问题，需要求解从起点出发，经过所有城市后回到起点的最短路程。可以使用动态规划来解决这个问题。

状态表示：dp[i][j] 表示当前在第 i 个城市，已经经过的城市集合为 j（二进制表示，从右往左第 i 位为 1 表示第 i 个城市已经经过，为 0 表示未经过），返回起点的最短路程。

状态转移：对于当前状态 dp[i][j]，枚举下一步要走的城市 k，如果 k 还没有经过，则转移方程为：dp[k][j|(1<<k)] = min(dp[k][j|(1<<k)], dp[i][j]+dist[i][k])，其中 dist[i][k] 表示 i 到 k 的距离。

最终的结果为 dp[0][(1<<n)-1]，表示从起点出发，访问所有城市后回到起点的最短路程。

以下是 C++ 代码实现：

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

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

int n, m;
int dist[MAXN][MAXN]; // 距离矩阵
int dp[MAXN][1<<MAXN]; // 状态表示和状态转移数组

int main()
{
    cin >> n >> m;

    // 初始化距离矩阵
    memset(dist, INF, sizeof(dist));
    for (int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--; // 将顶点编号从 0 开始
        dist[u][v] = dist[v][u] = w;
    }

    // 初始化状态转移数组
    memset(dp, INF, sizeof(dp));
    for (int i = 0; i < n; i++) {
        dp[i][1<<i] = 0; // 只经过 i 一个城市的情况
    }

    // 动态规划
    for (int j = 0; j < (1<<n); j++) { // 枚举经过的城市集合，从小到大枚举，保证状态转移时之前的状态已经被计算过
        for (int i = 0; i < n; i++) { // 枚举当前所在的城市
            if (!(j & (1<<i))) continue; // 如果当前城市不在经过的城市集合中，则跳过
            for (int k = 0; k < n; k++) { // 枚举下一步要走的城市
                if (j & (1<<k)) continue; // 如果下一步要走的城市已经在经过的城市集合中，则跳过
                dp[k][j|(1<<k)] = min(dp[k][j|(1<<k)], dp[i][j]+dist[i][k]); // 状态转移
            }
        }
    }

    // 输出结果
    int ans = INF;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[i][(1<<n)-1]+dist[i][0]); // 返回起点的最短路程
    }
    cout << ans << endl;

    return 0;
}

输入样例：

5 10
1 2 3
1 3 1
1 4 5
1 5 8
2 3 6
2 4 7
2 5 9
3 4 4
3 5 2
4 5 3

输出样例：

17