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.

Download