给定n个城市（从0到n-1），3元组[A, B, C]表示城市A和城市B之间存在道路，且成本为C。计算从0号城市出发，旅行完每个城市一遍，最后回到0号城市的最小成本与路径。如果不存在最优方案，输出-1.用C++写一段代码解决该问题

这是一个旅行商问题（TSP）的变种，可以使用动态规划（DP）来解决。具体思路如下：

1. 定义状态：令dp[i][j]表示从城市0出发，经过集合i中的城市，最后到达城市j的最小成本。

2. 初始化状态：dp[0][0] = 0，其他dp[i][j]初始化为无穷大。

3. 状态转移：对于任意的i和j，dp[i][j]的值可以由dp[i-{j}][k]+cost[k][j]转移而来，其中{k}表示集合i中除了j之外的所有城市，cost[k][j]表示从城市k到城市j的成本。

4. 最终答案：最终答案为dp[{0,1,2,...n-1}][0]，即从城市0出发，经过所有城市一遍，最后回到城市0的最小成本。

代码实现如下：

const int INF = 0x3f3f3f3f;
int dp[1<<20][20], cost[20][20];

int main() {
    int n; // 城市总数
    scanf("%d", &n);

    // 读入边权
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%d", &cost[i][j]);
        }
    }

    // 初始化状态
    memset(dp, INF, sizeof(dp));
    dp[1][0] = 0;

    // 状态转移
    for(int i=1; i<(1<<n); i++) { // 枚举集合
        for(int j=0; j<n; j++) { // 枚举最后一个城市
            if(i&(1<<j)) { // 集合i中包含城市j
                int pre = i^(1<<j); // 集合i中除了城市j之外的所有城市
                for(int k=0; k<n; k++) { // 枚举倒数第二个城市
                    if(pre&(1<<k)) { // 集合pre中包含城市k
                        dp[i][j] = min(dp[i][j], dp[pre][k]+cost[k][j]);
                    }
                }
            }
        }
    }

    // 输出答案
    int ans = INF;
    for(int i=0; i<n; i++) {
        ans = min(ans, dp[(1<<n)-1][i]+cost[i][0]);
    }
    if(ans == INF) printf("-1\n");
    else printf("%d\n", ans);

    return 0;
}