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.

Download