用c++语言【问题描述】 给定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个结点的序号） 【样例输入】 4 4 0 1 2 0 2 6 1 2 3 2 3 4 【样例输出】 -1 【样例说明】 输入的图为无向图，最小成本对应的路径优先选择序号小的结点，即第2个结点的序号<倒数第2个结点的序号 【评分标准】 5个测试用例，每个测试用例20分

以下是C++语言的代码实现，使用了Dijkstra算法和状态压缩DP。时间复杂度为O(n^2 * 2^n)。

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

const int INF = 0x3f3f3f3f;
const int MAXN = 20;
const int MAXM = 400;
const int MAXS = (1 << MAXN);

struct Edge {
    int to, cost;
    Edge(int to, int cost) : to(to), cost(cost) {}
};

vector<Edge> edges[MAXM];
int dist[MAXS][MAXN];
int pre[MAXS][MAXN];
int n, m;

void dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    memset(dist, INF, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    dist[1 << s][s] = 0;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (int i = 0; i < edges[u].size(); i++) {
            int v = edges[u][i].to;
            int w = edges[u][i].cost;
            for (int S = 0; S < (1 << n); S++) {
                if (!(S & (1 << v))) continue;
                int T = S ^ (1 << v);
                if (dist[S][u] + w < dist[T][v]) {
                    dist[T][v] = dist[S][u] + w;
                    pre[T][v] = u;
                    pq.push(make_pair(dist[T][v], v));
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back(Edge(v, w));
        edges[v].push_back(Edge(u, w)); // 无向图
    }
    dijkstra(0);
    int ans = INF, S = (1 << n) - 1, end = -1;
    for (int i = 1; i < n; i++) {
        if (dist[S][i] + edges[i][0].cost < ans) {
            ans = dist[S][i] + edges[i][0].cost;
            end = i;
        }
    }
    if (ans == INF) {
        cout << -1 << endl;
        return 0;
    }
    cout << ans << " ";
    vector<int> path;
    int state = S;
    while (end != -1) {
        path.push_back(end);
        int nextEnd = pre[state][end];
        state ^= (1 << end);
        end = nextEnd;
    }
    path.push_back(0);
    reverse(path.begin(), path.end());
    for (int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
    cout << endl;
    return 0;
}