Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=15;
      fi='';
      fo='';
      maxc=66000;
var n,re:longint;
    a:array[0..maxn,0..maxn] of longint;
    f:array[0..maxc,0..maxn] of longint;
    p:array[0..maxn] of longint;

procedure rf;
var i,j:byte;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     dec(n);
     for i:=0 to n do
     begin
          for j:=0 to n do
              read(a[i,j]);
          readln;
     end;
     close(input);
end;

procedure init;
var i:byte;
begin
     p[0]:=1;
     for i:=1 to n+1 do p[i]:=p[i-1]*2;
end;

function out(j,s:longint):boolean;
begin
     s:=(s shr j) and 1;
     out:=(s=0);
end;

function min(a,b:longint):longint;
begin
     if a<b then min:=a else min:=b;
end;

procedure pr;
var i,j,s,t,max:longint;
begin
     init;
     max:=p[n+1]-1;
     for i:=0 to max do
         for j:=0 to n do
             f[i,j]:=1000000;
     for i:=0 to n do
         f[p[i],i]:=0;
     for s:=1 to max do
         for i:=0 to n do
             if not out(i,s) then
                for j:=0 to n do
                    if out(j,s) then
                    begin
                         t:=s or p[j];
                         f[t,j]:=min(f[t,j],f[s,i]+a[i,j]);
                    end;
     re:=1000000;
     for i:=0 to n do
         if f[max,i]<re then re:=f[max,i];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <cstdio>

#define INF 1000000000

int f[80000][20], a[20][20], n;

int min( int a, int b ) {
    return a < b ? a : b; 
}

int F( int mask, int end ) {
    if ( mask == 0 ) return 0;
    int & res = f[mask][end];
    if ( res == 0 ) {
        res = INF;
        for( int i = 0; i < n; ++i )
            if ( mask & ( 1 << i ) )
                res = min( res, F(mask & ~( 1 << i ), i) + a[i][end] );
    }
    return res;
}

int main() {
    scanf( "%d", &n );
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j ) scanf( "%d", &a[i][j] );
    int res = INF;
    for( int i = 0; i < n; ++i )
        res = min(res, F((1<<n)-1, i));
    printf( "%d\n", res );
    return 0;
}

Code mẫu của ladpro98

program lem3;//dp;
uses    math;
const   fi='';
        oo=1000000;
        maxN=15;
var     c:array[1..maxN,1..maxN] of longint;
        f:array[1..maxN,0..(1 shl maxN)] of longint;
        pow:array[0..maxN] of longint;
        n:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        for j:=1 to n do
        read(inp,c[i,j]);
        close(inp);
end;

function getbit(i,j:longint):longint;
begin
        exit(i shr (j-1) and 1);
end;

procedure init;
var     i:longint;
begin
        pow[0]:=1;
        for i:=1 to n do
        pow[i]:=pow[i-1] shl 1;
end;

procedure dp;
var     i,j,k:longint;
begin
        for j:=1 to pow[n]-1 do
        for i:=1 to n do
        begin
                f[i,j]:=oo;
                for k:=1 to n do
                if k<>i then
                if getbit(j,k)=1 then
                f[i,j]:=min(f[i,j],f[k,j-pow[k-1]]+c[k,i]);
        end;
end;

procedure output;
var     i,j,res:longint;
begin
        res:=oo;
        for i:=1 to n do
        res:=min(res,f[i,pow[n]-1-pow[i-1]]);
        write(res);
end;

begin
        input;
        init;
        dp;
        output;
end.

Code mẫu của RR

{$R-,Q-}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=15;
  oo=1000000;
var
  t,n:longint;
  c:array[1..MAXN,1..MAXN] of longint;
  d:array[1..32767,1..15] of longint;
procedure inp; inline;
var
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do
  for j:=1 to n do
    read(f,c[i,j]);
  t:=1 shl n-1;
  close(f);
end;
procedure ans; inline;
var
  f:text;
  kq,i:longint;
begin
  assign(f,FOUT); rewrite(f);
  kq:=oo;
  for i:=1 to n do
    kq:=min(kq,d[t,i]);
  writeln(f,kq);
  close(f);
end;
procedure solve; inline;
var
  i,j,ii,jj:longint;
begin
  for i:=1 to t do
  for j:=1 to n do
    d[i,j]:=oo;
  for i:=1 to n do
    d[1 shl (i-1),i]:=0;
  for i:=1 to t do
  for j:=1 to n do
  if (i shr (j-1)) and 1=1 then
    begin
      ii:=i and (not (1 shl (j-1)));
      for jj:=1 to n do
        if (ii shr (jj-1)) and 1=1 then
          d[i,j]:=min(d[i,j],d[ii,jj]+c[jj,j]);
    end;
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của hieult

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

Code mẫu của ll931110

{$MODE DELPHI}
Program LEM3;
        Const
                input  = '';
                output = '';
                   max = 32767;
        Var
                  d: array[0..16] of integer;
                  a: array[1..16,1..16] of integer;
                  F: array[0..max,1..16] of integer;
                  n: integer;

Procedure init;
          Var
                 fi: text;
                i,j: integer;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Readln(fi, n);
                For i:= 1 to n do
                  For j:= 1 to n do read(fi, a[i,j]);

                Close(fi);
          End;

Procedure power;
          Var
                i: integer;
          Begin
                d[0]:= 1;
                For i:= 1 to n do d[i]:= d[i - 1] shl 1;
          End;

Procedure optimize;
          Var
                i,j,k,t,tmp: integer;
          Begin
                For i:= 0 to d[n] - 1 do
                  For j:= 1 to n do F[i,j]:= 1000000000;

                Fillchar(F[0], sizeof(F[0]), 0);
                For i:= 1 to n do F[d[i - 1],i]:= 0;

                For i:= 0 to d[n] - 1 do
                  For j:= 1 to n do if i and d[j - 1] = d[j - 1] then
                    Begin
                        t:= i - d[j - 1];
                        For k:= 1 to n do
                          if t and d[k - 1] = d[k - 1] then
                                Begin
                                        tmp:= F[t,k] + a[k,j];
                                        IF F[i,j] > tmp then F[i,j]:= tmp;
                                End;
                    End;
          End;

Procedure printresult;
          Var
                   fo: text;
                i,val: integer;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                val:= F[d[n] - 1,1];
                For i:= 2 to n do if val > F[d[n] - 1,i]
                                then val:= F[d[n] - 1,i];

                Writeln(fo, val);
                Close(fo);
          End;

Begin
        init;
        power;
        optimize;
        printresult;
End.

Code mẫu của skyvn97

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

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int n, c[20][20], f[1<<17][20];

int main() {
    cin >> n;
    for(int i=0;i<n;++i) for(int j=0;j<n;++j) cin >> c[i][j];
    memset( f, 0x1f, sizeof(f));
    for(int i=0;i<n;++i) f[1<<i][i] = 0;
    for(int b=1;b<(1<<n);++b)
        for(int i=0;i<n;++i) 
            for(int j=0;j<n;++j) if((b&(1<<j))==0)
                f[b|(1<<j)][j] <?= f[b][i] + c[i][j];
    cout << *min_element(f[(1<<n)-1], f[(1<<n)-1]+n) << endl;
    return 0;
}