记录编号	7660	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 埃雷萨拉斯的宝藏	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.851 s
提交时间	2008-11-10 21:36:31	内存使用	32.40 MiB

program cch(input,output);
const
 xx:array[1..4] of integer=(-1,0,1,0);
 yy:array[1..4] of integer=(0,1,0,-1);
var
 i,j,p,n,k,x1,y1,be,h,min:longint;
 map:array[1..50,1..50] of integer;
 flag:array[0..2600,0..2600] of boolean;
 a:array[0..2600,0..2600] of longint;
 djs,data:array[0..3000] of longint;
 s:array[0..3000] of boolean;
begin
 assign(input,'eldrethalas.in');
 assign(output,'eldrethalas.out');
 reset(input);
 rewrite(output);
 readln(n,p,h);
 for i:=1 to p do
  readln(data[i]);
 for i:=1 to n do
  for j:=1 to n do read(map[i,j]);
 for i:=0 to p+1 do
  for j:=0 to p+1 do
   flag[i,j]:=false;
 for i:=1 to n do
  for j:=1 to n do
   for k:=1 to 4 do
    begin
     x1:=i+xx[k]; y1:=j+yy[k];
     if (x1>=1)and(x1<=n)and(y1>=1)and(y1<=n) then
       if map[i,j]<>map[x1,y1] then
        begin
         flag[map[i,j],map[x1,y1]]:=true;
         flag[map[x1,y1],map[i,j]]:=true;
        end;
    end;
 for i:=1 to n do
  flag[0,map[1,i]]:=true;
 for i:=1 to n do
  flag[map[n,i],p+1]:=true;
 data[p+1]:=0;
 for i:=0 to p+1 do
  for j:=0 to p+1 do
   if flag[i,j] then
    a[i,j]:=data[j]
   else a[i,j]:=maxlongint;
 fillchar(s,sizeof (s),true);
 be:=0; s[0]:=false;
 for i:=1 to p+1 do djs[i]:=a[0,i];
 for i:=1 to p+1 do
  begin
   min:=maxlongint;
   for j:=0 to p+1 do
    if s[j] and (djs[j]<min) then
     begin
      min:=djs[j]; k:=j;
     end;
   s[k]:=false; be:=k;
   for j:=0 to p+1 do
    if flag[be,j] and (djs[j]>djs[be]+a[be,j]) then djs[j]:=djs[be]+a[be,j];
  end;
 if h-djs[p+1]>0 then write(h-djs[p+1])
  else write('NO');
 close(input);
 close(output);
end.