#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define check_i(i, node) ((1<<i) & node) //node第i位是不是有值,含第0位 #define MX 0x7f7f7f7f int n, w[11][11]; int dp[2<<10][11]; int main() { //freopen("1.txt", "r", stdin); while(scanf("%d", &n) && n) { memset(dp, 0x7f, sizeof(dp)); for(int i = 0;i <= n;i++) for(int j = 0;j <= n;j++) scanf("%d", &w[i][j]); for(int i = 0;i <= n;i++) for(int j = 0;j <= n;j++) for(int k = 0;k <= n;k++) if(w[j][k] > w[j][i] + w[i][k]) w[j][k] = w[j][i] + w[i][k]; int mx = (1<<n+1)-1; dp[0][0] = 0; for(int i = 0; i <= n;i++) { dp[(1<<i)][i] = w[0][i]; } for(int i = 1; i <= mx;i++) { for(int j = 0;j <= n;j++) { if(check_i(j, i)) { int k = (i & (~(1<<j))); if(i == (1<<j)) break; for(int z = 0;z <= n;z++) { if(check_i(z, k) && dp[i][j] > dp[k][z] + w[z][j]) dp[i][j] = dp[k][z] + w[z][j]; } } } } printf("%d\n", dp[mx][0]); } }