算法

(状压dp) $O(n \cdot 2^n)$

本题是状压dp入门题，做法和 ABC180E 基本一样

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

inline void chmin(int& x, int y) { if (x > y) x = y; }

int main() {
    int n;
    cin >> n;

    int n2 = 1<<n;
    const int INF = 1001001001;
    vector dp(n2, vector<int>(n, INF));
    vector dist(n, vector<int>(n));
    rep(i, n)rep(j, n) cin >> dist[i][j];
    for (int i = 1; i < n; ++i) {
        dp[1<<i][i] = dist[0][i];
    } 

    for (int s = 0; s < n2; s += 2) {
        rep(v, n) {
            if (~s>>v&1) continue;
            rep(u, n) {
                if (s>>u&1) continue;
                chmin(dp[s|1<<u][u], dp[s][v]+dist[v][u]);
            }
        }
    }

    cout << dp[n2-1][0] << '\n';

    return 0;
}