给定n个城市（从0到n-1），3元组[A, B, C]表示城市A和城市B之间存在道路，且成本为C。计算从0号城市出发，旅行完每个城市一遍，最后回到0号城市的最小成本与路径。如果不存在最优方案，输出-1. 【输入形式】 第一行有两个数n、m表示n个城市，m条边。 接下来的m行均为空格隔开的三个整数A B C，表示城市A和B之间的成本为C 【输出形式】 最小成本 最小成本对应的路径 【样例输入】 image.png 4 6 0 1 30 0 2 6 0 3 4 1 2 5 1 3 10 2 3 20 【样例输出】 25 0 2 1 3 0 （由于系统只支持一个答案，虽然 0 3 1 2 0 也可以，但是不是正确输出，正确答案中优先选择序号小的结点，即第2个结点的序号<倒数第2个结点的序号）C语言

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

#define INF 0x3f3f3f3f

int n, m, ans = INF;
int graph[20][20], vis[20], path[20];

void dfs(int cur, int cnt, int cost) {
    if (cnt == n && cur == 0) {
        if (cost < ans) {
            ans = cost;
            memcpy(path, vis, sizeof(vis));
        }
        return;
    }
    if (cost >= ans) return;
    for (int i = 0; i < n; i++) {
        if (graph[cur][i] != INF && !vis[i]) {
            vis[i] = cnt + 1;
            dfs(i, cnt + 1, cost + graph[cur][i]);
            vis[i] = 0;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    memset(graph, INF, sizeof(graph));
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        graph[a][b] = graph[b][a] = c;
    }
    vis[0] = 1;
    dfs(0, 1, 0);
    if (ans == INF) printf("-1");
    else {
        printf("%d\n0 ", ans);
        for (int i = 1; i < n; i++)
            printf("%d ", path[i]);
        printf("0");
    }
    return 0;
}

解释：

题目要求从0号城市出发，旅行完每个城市一遍，最后回到0号城市的最小成本与路径。

使用DFS搜索所有可能的路径，记录已经访问过的城市，当访问完所有的城市并回到0号城市时，更新最小成本和路径。

用一个vis数组记录已经访问过的城市，初始将0号城市设为已访问，并从0号城市开始搜索。

每个城市只能访问一次，所以搜索完当前城市所有的出边后，需要撤销对该城市的访问。

如果当前的路径成本已经大于等于当前最小成本，可以直接剪枝，不再继续搜索。

最后输出最小成本和最小成本对应的路径。