给定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 【输出形式】 最小成本 最小成本对应的路径 给出C++代码

以下是使用Dijkstra算法和状态压缩的代码实现：

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 16;
const int M = 1 << N;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[M][N];
int pre[M][N];

struct Node {
    int s, u, d;

    bool operator< (const Node& t) const {
        return d > t.d;
    }
};

void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    memset(pre, -1, sizeof pre);
    priority_queue<Node> q;
    q.push({1, 0, 0});
    dist[1][0] = 0;

    while (!q.empty()) {
        auto t = q.top();
        q.pop();

        int s = t.s, u = t.u, d = t.d;
        if (dist[s][u] < d) continue;

        for (int i = 0; i < n; i++) {
            int v = 1 << i;
            if (!(s & v)) continue;
            int w = g[u][i];
            if (w == -1) continue;
            int ns = s ^ v;
            if (dist[ns][i] > d + w) {
                dist[ns][i] = d + w;
                pre[ns][i] = u;
                q.push({ns, i, dist[ns][i]});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(g, -1, sizeof g);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
    }

    dijkstra();

    int res = INF, end = -1;
    for (int i = 1; i < n; i++) {
        if (g[i][0] == -1) continue;
        int s = (1 << n) - 1;
        if (dist[s ^ 1][i] == INF) continue;
        if (res > dist[s ^ 1][i] + g[i][0]) {
            res = dist[s ^ 1][i] + g[i][0];
            end = i;
        }
    }

    if (res == INF) {
        cout << "-1\n";
        return 0;
    }

    cout << res << "\n0 ";
    int s = (1 << n) - 1, u = end;
    while (s) {
        int t = pre[s][u];
        s ^= 1 << u;
        cout << u << " ";
        u = t;
    }
    cout << "0\n";

    return 0;
}

其中，`dist[s][u]`表示状态为`s`，当前在城市`u`的最小花费；`pre[s][u]`表示状态为`s`，当前在城市`u`时，从哪个城市转移来的。

初始状态为`s=1`（即只有起点被访问），最终状态为`s=(1<<n)-1`（即所有城市都被访问过了）。对于每个状态`s`和城市`u`，枚举下一个要访问的城市`v`，如果`v`在`s`中且从`u`到`v`有路径，则更新`dist[ns][v]`和`pre[ns][v]`。其中，`ns=s^v`表示状态`s`去掉了`v`。

最后，枚举每个城市`i`，如果从`i`到起点`0`有路径，则找到一个状态`s`，使得所有城市都被访问过且不包括起点`0`，且从`0`到`i`再回到`0`的总花费最小。输出最小花费和路径即可。

时间复杂度为$O(n^2 2^n \log n)$。