CHNREST - Chinese restaurant

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$R+,Q+}
{$Mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       60000;

var
  f1,f2         :       text;
  f             :       array[0..15,0..MAXN] of longint;
  save          :       array[0..MAXN] of longint;
  lt3           :       array[0..10] of longint;

  deg,cost      :       array[1..30] of longint;
  ke,dd         :       array[1..30,1..30] of longint;

  n,m,m1        :       longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i,v:longint;
    begin
      read(f1,m,n);
      for i:=1 to m do
        read(f1,cost[i]);
      readln(f1);
      for i:=1 to n do
        begin
          while not seekeoln(f1) do
            begin
              read(f1,v);
              if dd[v,i]=1 then continue;
              inc(deg[v]);
              ke[v,deg[v]]:=i;
              dd[v,i]:=1;
            end;
          readln(f1);
        end;
    end;

procedure qhd(start,len:longint);
    var
      i,last,j,now,u,v:longint;
    begin
      fillchar(f,sizeof(f),$77);
      f[0,0]:=0;
      for i:=0 to len-1 do
      for last:=0 to lt3[n]-1 do
      if f[i,last]<1000111000 then
        begin
          u:=start+i+1;
          f[i+1,last]:=min(f[i+1,last],f[i,last]);
          now:=last;
          for j:=1 to deg[u] do
            begin
              v:=ke[u,j];
              if (last mod lt3[v]) div lt3[v-1]=2 then
                begin
                  now:=-1;
                  break;
                end;
              now:=now+lt3[v-1];
            end; //for v
          if now=-1 then continue;
          f[i+1,now]:=min(f[i+1,now],f[i,last]+cost[u]);
        end; //for u,last
    end;

procedure solve;
    var
      i,res:longint;
    begin
      lt3[0]:=1;
      for i:=1 to 10 do lt3[i]:=lt3[i-1]*3;

      m1:=m>>1;
      qhd(0,m1);
      for i:=0 to lt3[n]-1 do
        save[i]:=f[m1,i];
      qhd(m1,m-m1);
      res:=high(longint);
      for i:=0 to lt3[n]-1 do
        res:=min(res,int64(save[i])+f[m-m1,lt3[n]-1-i]);
      if res>high(longint) div 2 then writeln(f2,-1) else writeln(f2,res);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Download