【问题描述】 给定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++的代码

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

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

struct Edge {
    int to, w;
    Edge(int _to, int _w) : to(_to), w(_w) {}
};

vector<Edge> G[MAXN];
int dist[MAXN][1 << MAXN]; // 记忆化

int tsp(int u, int state, int n) {
    if (state == (1 << n) - 1) { // 已经经过了所有城市，回到起点
        return G[u][0].w;
    }
    if (dist[u][state] != INF) { // 已经计算过
        return dist[u][state];
    }
    int res = INF;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i].to;
        int w = G[u][i].w;
        if (!(state & (1 << v))) { // 如果城市v还没访问过
            res = min(res, tsp(v, state | (1 << v), n) + w);
        }
    }
    return dist[u][state] = res; // 记忆化
}

int main() {
    int n, m;
    cin >> n >> m;
    memset(dist, INF, sizeof(dist));
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
    }
    int ans = tsp(0, 1, n);
    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}