【題解】TIOJ 1418 . 交大都是雷

#include <iostream>
#include <cmath>
using namespace std;

int t, n, a[22][22];
string s;
double dp[1<<22];

int cost(int A, int b, int c){
    int ret = a[A][b] + a[A][c] + a[b][c];
    return ret;
}

int solve(int mask){
    if (dp[mask] > -1) return dp[mask];
    if (!mask) return 0;
    int mn = 1e9;
    for (int i = 0; i < n; i++){
        if (!((1<<i) & mask)) continue;
        for (int j = i+1; j < n; j++){
            if (!((1<<j) & mask)) continue;
            for (int k = j+1; k < n; k++){
                if (!((1<<k) & mask)) continue;
                mn = min(mn, solve(mask ^ (1<<i) ^ (1<<j) ^ (1<<k))+cost(i, j, k));
            }
        }
        break;
    }
    return dp[mask] = mn;
}

int main() {
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                cin >> a[i][j];
            }
        }
        for (int i = 0; i < (1<<n); i++){
            dp[i] = -1;
        }
        cout << solve((1<<n)-1) << "\n";
    }
}