【问题描述】 给定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算法的C++代码实现：

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

const int INF = 0x3f3f3f3f;

struct Edge {
    int from, to, dist;
    Edge(int u, int v, int d) : from(u), to(v), dist(d) {}
};

struct HeapNode {
    int d, u;
    HeapNode(int dist, int node) : d(dist), u(node) {}
    bool operator < (const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

class Dijkstra {
public:
    Dijkstra(int n) : dist(n, INF), vis(n, false), p(n, -1) {}
    void addEdge(int u, int v, int w) {
        edges.push_back(Edge(u, v, w));
        int m = edges.size();
        G[u].push_back(m - 1);
    }
    void solve() {
        priority_queue<HeapNode> q;
        q.push(HeapNode(0, 0));
        dist[0] = 0;
        while (!q.empty()) {
            HeapNode x = q.top();
            q.pop();
            int u = x.u;
            if (vis[u])
                continue;
            vis[u] = true;
            for (int i = 0; i < G[u].size(); i++) {
                Edge& e = edges[G[u][i]];
                if (dist[e.to] > dist[u] + e.dist) {
                    dist[e.to] = dist[u] + e.dist;
                    p[e.to] = G[u][i];
                    q.push(HeapNode(dist[e.to], e.to));
                }
            }
        }
    }
    int getDist() const {
        return dist[0];
    }
    vector<int> getPath() const {
        vector<int> path;
        int u = 0;
        while (u != -1) {
            path.push_back(u);
            u = edges[p[u]].from;
        }
        reverse(path.begin(), path.end());
        if (path.size() != dist.size())
            path.clear();
        return path;
    }

private:
    vector<Edge> edges;
    vector<int> G[1000];
    vector<int> dist;
    vector<bool> vis;
    vector<int> p;
};

int main() {
    int n, m;
    cin >> n >> m;
    Dijkstra dijkstra(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dijkstra.addEdge(u, v, w);
        dijkstra.addEdge(v, u, w);
    }
    dijkstra.solve();
    int ans = dijkstra.getDist();
    if (ans == INF)
        cout << -1 << endl;
    else {
        cout << ans << endl;
        vector<int> path = dijkstra.getPath();
        for (int i = 0; i < path.size(); i++) {
            if (i > 0)
                cout << "->";
            cout << path[i];
        }
        cout << "->0" << endl;
    }
    return 0;
}

其中，Dijkstra类封装了Dijkstra算法的实现，addEdge方法用于添加边，solve方法用于求解最短路径，getDist方法返回最短路径的长度，getPath方法返回最短路径的节点序列。在主函数中，首先读入输入数据，然后调用Dijkstra类的solve方法求解最短路径，最后输出最短路径的长度和节点序列。若不存在最优方案，则输出-1。