LEM3 - TRIP
Tác giả: RR
Ngôn ngữ: Pascal
{$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.