LEM3 - TRIP
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#define INF 1e9
#define MAX 22
int c[MAX][MAX];
int f[MAX][100100];
int n;
void init(void) {
int i,j;
scanf("%d",&n);
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1)
scanf("%d",&c[i][j]);
for (i=1;i<=n;i=i+1)
for (j=0;j<(1<<n);j=j+1)
f[i][j]=INF;
}
int r(int i,int s) {
if ((s|(1<<(i-1)))!=s) return (INF);
if (s==(1<<(i-1))) return (0);
if (f[i][s]<INF) return (f[i][s]);
int j,t;
for (j=1;j<=n;j=j+1)
if ((i!=j) && ((s|(1<<(j-1)))==s)) {
t=r(j,s&((1<<n)-1-(1<<(i-1))))+c[j][i];
if (f[i][s]>t) f[i][s]=t;
}
return (f[i][s]);
}
void process(void) {
int m=INF;
int i;
for (i=1;i<=n;i=i+1)
if (m>r(i,(1<<n)-1)) m=r(i,(1<<n)-1);
printf("%d",m);
}
int main(void) {
init();
process();
}