RT，状压求解旅行商问题，图以邻接矩阵的形式给出，$n \le 18, G_{i,j} \begin{cases} =0 & i=j \\ \le10000 & i\ne j\\ \end{cases}$，其中 $G_{i,j}$ 表示点 $i$ 到点 $j$ 的距离。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define mkp make_pair
#define F first
#define S second
int G[20][20], n;
ll dp[1 << 19][20];
inline int lowbit(int x) {
	return x & (-x);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	memset(G, 0x3f, sizeof(G));
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> G[i][j];
	dp[1][1] = 0;
	for (int i = 1, ii = 1; i < (1 << n); i++, ii++) {
		while (ii) {
			int k = lowbit(ii);
			ii -= k;
			int j = 0;
			while (k) {
				k >>= 1;
				j++;
			}
			for (k = 0; k < n; k++) {
				int a = 1 << k, b = i & a;
				if (!b) dp[i + a][k + 1] = min(dp[i + a][k + 1], dp[i][j] + G[j][k + 1]);
			}
		}
	}
	ll ans = LLONG_MAX;
	for (int i = 2; i <= n; i++) if (G[i][1] != 0x3f3f3f3f) ans = min(ans, dp[(1 << n) - 1][i] + G[i][1]);
	cout << ans;
	return 0;
}