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++的实现，使用了Dijkstra算法和状态压缩DP：

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

const int N = 20, M = 1 << N;
const int INF = 1e9;

int n, m;
int g[N][N];
int f[M][N];
bool st[M][N];

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

int dijkstra(int u, int v)
{
    memset(st, 0, sizeof st);
    memset(f, 0x3f, sizeof f);

    priority_queue<Node> heap;
    heap.push({u, 0});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int u = t.u, d = t.d;
        if (st[u][d]) continue;
        st[u][d] = true;

        for (int i = 0; i < n; i ++ )
            if (g[d][i] != INF)
            {
                int w = g[d][i];
                if (i == v && u + (1 << i) == (1 << n) - 1)
                    return f[u][d] + w;
                int v = u | (1 << i);
                if (f[u][d] + w < f[v][i])
                {
                    f[v][i] = f[u][d] + w;
                    heap.push({v, i});
                }
            }
    }

    return INF;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < n; i ++ ) g[i][i] = 0;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = min(g[a][b], w);
    }

    int res = INF, path[N];
    for (int i = 0; i < n; i ++ )
    {
        int t = dijkstra(1 << i, i);
        if (t < res)
        {
            res = t;
            path[0] = i;
            int u = (1 << i), d = i;
            for (int j = 1; j < n; j ++ )
                for (int k = 0; k < n; k ++ )
                    if ((u >> k & 1) && g[d][k] + f[u][d] == f[u][k])
                    {
                        path[j] = k;
                        u |= 1 << k;
                        d = k;
                        break;
                    }
        }
    }

    if (res == INF) puts("-1");
    else
    {
        cout << res << ' ';
        for (int i = 0; i < n; i ++ ) cout << path[i] << ' ';
        cout << endl;
    }

    return 0;
}

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