Chương trình C++ tính chi phí đi qua tất cả tọa độ 3D và quay về đầu

Mô tả bài toán

Cho n tọa độ 3D. Chi phí từ (a,b,c) đến (x,y,z) = |x-a|+|y-b|+max(0,z-c). Bắt đầu từ tọa độ 0, thăm tất cả ít nhất 1 lần, quay về tọa độ 0. Tìm chi phí nhỏ nhất (TSP bitmask DP).

Ví dụ

n=3, coords={{1,1,0},{1,3,4},{3,2,2}}. Đầu ra: 12.

Thuật toán (Held-Karp DP bitmask)

1. dp[mask][last] = chi phí nhỏ nhất đi qua tập mask kết thúc tại last.
2. Khởi tạo .
3. Chuyển trạng thái: từ thử thêm chưa trong mask: .
4. Kết quả: min trên của .

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

const int INF=1e9;

int solve(int n,vector<tuple<int,int,int>> coords){
    vector<vector<int>> dp(1<