Cod sursa(job #320767)
#include <stdio.h>
#define maxN 20
#define maxM 10000
#define oo (int) 1e9
int A[maxN][maxN], ind[maxN], C[maxM][maxN], N;
inline int min (int a, int b) { if (a < b) return a; return b; }
inline int max (int a, int b) { if (a > b) return a; return b; }
void baga_marfa (int mask) {
int Size = 0, j, k, p, q, nowp, nowq;
for (j = 0; j < N; ++ j)
if (mask & (1 << j))
ind[ ++ Size ] = j + 1;
for (j = 1; j < (1 << Size) - 1; ++ j) {
k = 0;
for (p = 0; p < Size; ++ p)
if ( (j & (1 << p) ) != 0)
k += 1 << (ind[p + 1] - 1);
for (p = 1; p <= Size; ++ p)
if ( ( (1 << (ind[p] - 1) ) & k ) == 0 )
for (q = 1; q <= Size; ++ q) {
nowp = ind[p];
nowq = ind[q];
if (p != q && ( (1 << (nowq - 1) ) & k) != 0)
C[mask][nowp] = min(C[mask][nowp], A[nowp][nowq] + max(C[k][nowq], C[mask - k][nowp]));
}
}
}
void solve () {
int i, j;
// initializare :
for (i = 0; i < (1 << N); ++ i)
for (j = 1; j <= N; ++ j)
C[i][j] = oo;
for (i = 1; i <= N; ++ i) C[1 << (i - 1)][i] = 0;
// pentru fiecare configuratie bag dinamica
for (i = 0; i < (1 << N); ++ i) {
baga_marfa (i);
}
printf("%d\n", C[(1 << N) - 1][1]);
}
int main () {
int i, j, T;
freopen("cast.in", "r", stdin);
freopen("cast.out", "w", stdout);
for (scanf("%d", &T); T -- ;) {
scanf("%d", &N);
for (i = 1; i <= N; ++ i)
for (j = 1; j <= N; ++ j)
scanf("%d", &A[i][j]);
solve ();
}
return 0;
}