百练 4124: 海贼王之伟大航路

航路"/>

百练 4124: 海贼王之伟大航路

状压dp

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;const int N = 20;int mp[N][N];
int dp[1 << N][N];int main() {int n; scanf("%d", &n);for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf("%d", &mp[i][j]);memset(dp, 0x3f, sizeof(dp));dp[1][0] = 0;for (int i = 1; i < (1 << n); i++) {for (int k = 0; k < n; k++) {if ((i >> k) & 1) {for (int j = 0; j < n; j++) {if ((i >> j) & 1) continue;dp[i | (1 << j)][j] = min(dp[i][k] + mp[k][j], dp[i | (1 << j)][j]);}}}}printf("%d\n", dp[(1 << n) - 1][n - 1]);return 0;
}