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 【输出形式】 最小成本 最小成本对应的路径 【样例输入】 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 说明：正确答案中优先选择序号小的结点，即第2个结点的序号<倒数第2个结点的序号

以下是C++的代码实现，使用了Prim算法求解最小生成树，再通过回溯法求解哈密顿回路：

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

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

struct Edge {
    int from, to, weight;
    Edge(int _from, int _to, int _weight) : from(_from), to(_to), weight(_weight){}
    bool operator < (const Edge& e) const {
        return weight > e.weight; // 小根堆
    }
};

int n, m;
vector<Edge> edges; // 存储边的信息
vector<int> G[MAXN]; // 存储每个点出发的边的编号
int d[MAXN][1 << MAXN]; // d[i][S]表示从0号点出发，经过集合S中的点，最后到达点i的最小花费
int p[MAXN][1 << MAXN]; // 记录d[i][S]的最后一步走的边
int path[MAXN]; // 存储最优路径

void init() {
    memset(d, INF, sizeof(d));
    memset(p, -1, sizeof(p));
    for(int i=0;i<MAXN;i++) G[i].clear();
    edges.clear();
}

void addEdge(int u, int v, int w) {
    edges.emplace_back(u, v, w);
    int m = edges.size();
    G[u].push_back(m-1);
    G[v].push_back(m-1);
}

void prim() {
    priority_queue<Edge> q;
    bool vis[MAXN] = {false};
    d[0][1] = 0; // 从0号点出发，集合S中只有0号点
    q.push(Edge(-1, 0, 0)); // 从-1到0的边，边权为0
    while(!q.empty()) {
        Edge e = q.top(); q.pop();
        int u = e.to;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i=0;i<G[u].size();i++) {
            Edge& e = edges[G[u][i]];
            int v = e.from + e.to - u; // 从u到v的边
            if(!vis[v] && e.weight < d[v][(1<<n)-1]) {
                d[v][(1<<n)-1] = e.weight;
                p[v][(1<<n)-1] = G[u][i];
                q.push(Edge(-1, v, d[v][(1<<n)-1]));
            }
        }
    }
}

void dfs(int u, int S, int& cnt) {
    path[cnt++] = u;
    if(S == (1<<n)-1 && u == 0) return;
    int e = p[u][S];
    int v = edges[e].from + edges[e].to - u;
    dfs(v, S^(1<<v), cnt);
}

int main() {
    cin >> n >> m;
    init();
    for(int i=0;i<m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    prim();
    if(d[0][(1<<n)-1] == INF) {
        cout << -1 << endl;
        return 0;
    }
    int cnt = 0;
    dfs(0, (1<<n)-1, cnt);
    cout << d[0][(1<<n)-1] << " ";
    for(int i=0;i<cnt;i++) {
        if(i) cout << " ";
        cout << path[i];
    }
    cout << endl;
    return 0;
}

时间复杂度为$O(n^2 2^n + m \log m)$，其中$n^2 2^n$是状态数，$m \log m$是Prim算法的时间复杂度。