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.

Download