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();
}

Download