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.