โปรแกรม C++ หาค่าใช้จ่ายการเดินทางครบพิกัด 3 มิติ

มีพิกัด 3 มิติ n จุด ค่าใช้จ่ายจาก (a,b,c) ไป (x,y,z) คือ |x-a| + |y-b| + max(0, z-c) เริ่มจากจุดแรก เดินครบทุกจุดอย่างน้อย 1 ครั้ง กลับมาจุดแรก หาค่าใช้จ่ายรวมน้อยที่สุด (TSP แบบ DP bitmask)

ตัวอย่าง: n=3, coords={{1,1,0},{1,3,4},{3,2,2}} ผลลัพธ์: 12

ขั้นตอนการแก้ปัญหา (Held-Karp DP / Bitmask TSP)

1. DP state tpa[mask][last] = ค่าใช้จ่ายน้อยที่สุดไปเยี่ยมชุด mask จบที่ last
2. เริ่ม tpa[1][0] = 0 (mask=1 หมายถึงจุด 0)
3. วน mask = 1 ถึง 2^n-1 (เฉพาะ mask ที่ bit 0 = 1) สำหรับทุก j ใน mask ลองต่อยอดไป t คำนวณค่าใช้จ่ายเพิ่ม
4. คำตอบ = min over i ของ tpa[2^n-1][i] + cost(i→0)

ตัวอย่างโค้ด C++

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

const int INF = 1e9;
#define N 100

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