Editorial for TRIP

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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);
dec(n);
for i:=0 to n do
begin
for j:=0 to n do
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;
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;
}


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);
for i:=1 to n do
for j:=1 to n do
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.


{$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);

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