LEM3 - TRIP
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
int f[70000][17];
int main()
{
// freopen("LEM3.in","r",stdin);
int n, a[17][17],b[17],chay=1;
scanf("%d",&n);
for(int i = 0;i<n;i++)
for(int j = 0;j<n;j++)
scanf("%d",&a[i][j]);
for(int i = 0;i<n;i++)
f[0][i] = 0;
b[0] = 1;
for(int i = 1;i<n;i++)
{
b[i] = b[i-1]*2;
chay = chay + b[i];
}
for(int i = 1;i<=chay;i++)
{
int t[n],m= i;
for(int j = 0;j<n;j++)
{
t[j] = m%2;
m = m/2;
}
for(int j = 0;j<n;j++)
{
if(t[j]==0)
f[i][j]=0;
else
{
int min = 1000000;
for(int k = 0;k<n;k++)
if(f[i-b[j]][k]+a[k][j] < min && t[k]!=0 && k!=j)
min = f[i-b[j]][k]+a[k][j];
if(min == 1000000) f[i][j] = 0;
else f[i][j] = min;
}
}
}
int Min = 1000000;
for(int i = 0;i<n;i++)
if(f[chay][i]<Min)
Min =f[chay][i];
printf("%d",Min);
// getch();
}