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