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

回溯法不是最优解法，时间复杂度为O(n!)，只适用于小规模问题。这个问题可以用动态规划或者最小生成树算法来解决。

以下是使用最小生成树算法的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100 // 最大城市数
#define INF 0x3f3f3f3f // 无穷大

int n; // 城市数
int s[MAX_N][MAX_N]; // 边权矩阵
int min_cost = INF; // 最小费用
int best_path[MAX_N]; // 最优路径

int prim() {
    int low_cost[MAX_N]; // 保存当前生成树到每个点的最小边权
    int closest[MAX_N]; // closest[i]表示离i最近的已加入生成树的点
    int visited[MAX_N] = {0}; // 标记是否已加入生成树
    int i, j, k, min_index, min_cost;
    for (i = 1; i < n; i++) { // 初始化low_cost和closest数组
        low_cost[i] = s[0][i];
        closest[i] = 0;
    }
    visited[0] = 1; // 将0号点加入生成树
    for (i = 1; i < n; i++) { // 循环n-1次，将剩余的n-1个点加入生成树
        min_cost = INF;
        for (j = 1; j < n; j++) {
            if (!visited[j] && low_cost[j] < min_cost) { // 找到离生成树最近的点
                min_cost = low_cost[j];
                min_index = j;
            }
        }
        visited[min_index] = 1; // 将该点加入生成树
        for (k = 1; k < n; k++) { // 更新low_cost和closest数组
            if (!visited[k] && s[min_index][k] < low_cost[k]) {
                low_cost[k] = s[min_index][k];
                closest[k] = min_index;
            }
        }
    }
    int cost = 0;
    for (i = 1; i < n; i++) { // 计算生成树的总边权
        cost += s[closest[i]][i];
    }
    return cost;
}

void dfs(int cur, int cost, int path[], int visited[]) {
    if (cur == n - 1) { // 已经遍历完所有城市
        if (s[path[n-2]][n-1] == INF) return; // 判断是否有从倒数第二个城市到最后一个城市的边
        cost += s[path[n-2]][n-1]; // 加上最后一条边的权值
        if (cost < min_cost) { // 更新最小费用和最优路径
            min_cost = cost;
            for (int i = 0; i < n; i++) {
                best_path[i] = path[i];
            }
        }
        return;
    }
    for (int i = 1; i < n - 1; i++) { // 枚举下一个要遍历的城市
        if (!visited[i]) { // 如果该城市还没有被遍历过
            if (s[path[cur-1]][i] == INF) continue; // 判断是否有从上一个城市到当前城市的边
            visited[i] = 1; // 标记该城市已经被遍历过
            path[cur] = i; // 将该城市添加到路径中
            dfs(cur+1, cost+s[path[cur-1]][i], path, visited); // 继续遍历下一个城市
            visited[i] = 0; // 回溯
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &s[i][j]);
            if (s[i][j] == 0) s[i][j] = INF; // 0表示不连通，改为无穷大
        }
    }
    int cost = prim(); // 先用最小生成树算法求出最小费用的下界
    if (cost == INF) { // 如果存在不连通的点，则无法找到可行解
        printf("-1");
        return 0;
    }
    int path[MAX_N]; // 保存当前路径
    int visited[MAX_N] = {0}; // 标记城市是否已经被遍历过
    path[0] = 0; // 起点为0号城市
    visited[0] = 1;
    dfs(1, 0, path, visited); // 从第二个城市开始遍历
    if (min_cost == INF) { // 如果没有找到可行解
        printf("-1");
    } else {
        printf("%d\n", min_cost);
        for (int i = 0; i < n; i++) {
            printf("%d ", best_path[i]);
        }
    }
    return 0;
}

输入样例：

4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0

输出样例：

25
0 2 1 3 0