leetcode-go/bailian/4124.one-piece/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 16;

int w[N][N];
int dp[1 << N][N];
int n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
  memset(dp, 0x3F, sizeof(dp));  // Set dp[i][j] as 0x3F3F3F3F
  dp[1][0] = 0;
  for (int i = 1, fin = (1 << n) - 1; i <= fin; i++)
    for (int j = 0, j_ = 1; j < n; j++, j_ <<= 1)
      if (j_ & i)
        for (int k = 0, k_ = 1; k < n; k++, k_ <<= 1)
          if (k_ & i && k != j)
            dp[i][k] = min(dp[i][k], dp[i ^ k_][j] + w[j][k]);
  printf("%d\n", dp[(1 << n) - 1][n - 1]);
  return 0;
}