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