#include <stdio.h> #include <limits.h> #define MAXN 16 #define INF INT_MAX int n; int dist[MAXN][MAXN]; int dp[1 << MAXN][MAXN]; #define MIN(a, b) ((a) < (b) ? (a) : (b)) int tsp(int mask, int pos) { if (mask == (1 << n) - 1) { return dist[pos][0]; } if (dp[mask][pos] != -1) { return dp[mask][pos]; } int answer = INF; for (int city = 0; city < n; city++) { if ((mask & (1 << city)) == 0) { int newAnswer = dist[pos][city] + tsp(mask | (1 << city), city); answer = MIN(answer, newAnswer); } } return dp[mask][pos] = answer; } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &dist[i][j]); } } for (int i = 0; i < (1 << n); ++i) { for (int j = 0; j < n; ++j) { dp[i][j] = -1; } } int result = tsp(1, 0); printf("%d\n", result); return 0; }