最坑的还是,我150分里的100分是第四题……
(我本来预计第四题拿50分算多的了……)
另外,第1题3个点,第2题2个点,第3题0个点……
dfs秒过
type new=array[0..110] of longint;
var n,k,m,s,t,i,j,u,v,num,ans,may,ka:longint;
now,c:new;
a,no:array[0..110,0..110] of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function pd(x:longint):boolean;
var i:longint;
begin
for i:=1 to k do begin
if (now[i]=1)and(no[x,i]=1) then exit(false);
end;
exit(true);
end;
procedure dfs(step,sum:longint);
var i:longint;
begin
if step=t then ans:=min(ans,sum) else begin
if sum>=ans then exit;
if ka>=m then begin
writeln(-1);
halt;
end;
for i:=step+1 to n do begin
if (a[step,i]<1000)and(now[c[i]]=0)and(pd(i)) then begin
now[c[i]]:=1;
inc(ka);
dfs(i,sum+a[step,i]);
// dec(ka);
now[c[i]]:=0;
end;
end;
end;
end;
begin
assign(input,'culture.in');
assign(output,'culture.out');
reset(input);
rewrite(output);
readln(n,k,m,s,t);
fillchar(a,sizeof(a),$7f);
for i:=1 to n do read(c[i]);
for i:=1 to k do begin
for j:=1 to k do read(no[i,j]);
readln;
end;
for i:=1 to m do begin
readln(u,v,may);
if may<a[v,u] then begin
a[u,v]:=may;
a[v,u]:=may;
end;
end;
if a[t,s]=1 then begin
writeln(-1);
exit;
end;
ans:=maxlongint;
dfs(s,0);
if ans=maxlongint then ans:=-1;
writeln(ans);
close(input);
close(output);
end.