某销售员要到n个城市去推销商品，已知各城市之间的路程（或旅费）s。售货员选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总的路程（或总旅费）最小。设G=(V,E)是一个带权图。图中的各边的费用（权）为正数。图中的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题是指在图G中找出费用最小的周游路线。如果找不到可行方案，则输出-1。 输入 第一行城市的数量n。 接下来每行输入各城市之间的路程（旅费）。（假设起点即驻地为1号顶点） 输出 第一行最短路程（或最少旅费） 第二行最短路程（或费用最小）的周游路线 样例输入 4 1 2 30 1 3 6 1 4 4 2 3 5 2 4 10 3 4 20 样例输出 25 1 3 2 4 1 用C语言编写，用回溯法实现

回溯法不是最优解法，这里提供一种更适合解决旅行售货员问题的算法——简单的动态规划。以下是C语言代码实现：

#include <stdio.h>
#define INF 0x3f3f3f3f

int n, m;
int w[20][20];
int dp[1<<16][16];
int pre[1<<16][16];

int min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    scanf("%d", &n);
    m = 1 << n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &w[i][j]);
        }
    }
    // 初始化
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0; // 起点为0号城市
    // 动态规划
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) { // 判断城市j是否在i中
                for (int k = 0; k < n; k++) {
                    if (i & (1 << k) && j != k) { // 判断城市k是否在i中且不等于j
                        if (dp[i-(1<<j)][k] + w[k][j] < dp[i][j]) {
                            dp[i][j] = dp[i-(1<<j)][k] + w[k][j];
                            pre[i][j] = k; // 记录路径
                        }
                    }
                }
            }
        }
    }
    // 输出最短路程
    int ans = INF;
    int end = -1;
    for (int i = 1; i < n; i++) {
        if (dp[m-1][i] + w[i][0] < ans) {
            ans = dp[m-1][i] + w[i][0];
            end = i;
        }
    }
    if (ans == INF) {
        printf("-1");
    } else {
        printf("%d\n", ans);
        // 输出路径
        int path[20], cnt = 0;
        int x = m-1, y = end;
        while (x > 0) {
            path[cnt++] = y;
            int tmp = y;
            y = pre[x][y];
            x = x - (1<<tmp);
        }
        printf("1 ");
        for (int i = cnt-1; i >= 0; i--) {
            printf("%d ", path[i]+1); // 加1是为了输出城市编号
        }
        printf("1");
    }
    return 0;
}

思路：

1. 输入城市数量和城市之间的路程（或旅费）。
2. 初始化dp数组，dp[i][j]表示经过i集合中的城市，以j为结尾的最短路程。
3. 动态规划。状态转移方程为：dp[i][j] = min(dp[i-(1<<j)][k]+w[k][j])，其中i-(1<<j)表示把城市j从集合i中去掉，k为i中的其他城市。
4. 输出最短路程。遍历dp[m-1][i]+w[i][0]（i从1到n-1），找到最小值，即为最短路程。如果不存在可行方案，则输出-1。
5. 输出最短路线。根据pre数组记录的路径逆推出最短路线。