记录编号	7589	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 埃雷萨拉斯的宝藏	最终得分	100
用户昵称	francis	是否通过	通过
代码语言	Pascal	运行时间	0.187 s
提交时间	2008-11-10 18:34:16	内存使用	54.35 MiB

program eldrethalas;
const
fin='eldrethalas.in';
fou='eldrethalas.out';
max=300000000;
g:array[1..4,1..2]of longint=((-1,0),(0,1),(1,0),(0,-1));
var
t:array[0..51,0..51]of longint;
a,e:array[0..2510,0..2510]of longint;
b:array[0..2510,0..2510]of boolean;
l,dis,w:array[0..2510]of longint;
bo:array[0..2510]of boolean;
d:array[0..20000]of longint;
t1,t2,k,p,q,x,y,i,j,n,m,h:longint;
f1,f2:text;

procedure init;
begin
assign(f1,fin);
assign(f2,fou);
reset(f1); rewrite(f2);
read(f1,n,m,h);
for i:=1 to m do
read(f1,w[i]);

for i:=1 to n do
for j:=1 to n do
read(f1,t[i,j]);

for i:=1 to n do
t[n+1,i]:=m+1;

for i:=0 to n do
for j:=1 to n do
begin
 p:=t[i,j]; b[p,p]:=true;
 for k:=1 to 4 do
 begin
  x:=i+g[k,1]; y:=j+g[k,2];
  if (x>0)and(x<=n+1)and(y>0)and(y<=n) then
   begin
    q:=t[x,y];
    if b[p,q]=false then begin
                             inc(l[p]);
                             a[p,l[p]]:=q; b[p,q]:=true;
                             e[p,l[p]]:=w[q];
                         end;
   end;
 end;
end;
inc(m);
for i:=1 to m do
dis[i]:=max;
end;

procedure spfa;
begin
d[1]:=0; bo[0]:=true; t1:=1; t2:=1;
while t1<=t2 do
begin
 k:=d[t1];
 for i:=1 to l[k] do
 begin
  if dis[a[k,i]]>dis[k]+e[k,i] then
     begin
      dis[a[k,i]]:=dis[k]+e[k,i];
      if bo[a[k,i]]=false then
        begin
          inc(t2);
          d[t2]:=a[k,i];
          bo[a[k,i]]:=true;
        end;
     end;
 end;
 inc(t1); bo[k]:=false;
end;
end;

procedure print;
begin
h:=h-dis[m];
if h<=0 then write(f2,'NO') else write(f2,h);
close(f1); close(f2);
end;

begin
init;
spfa;
print;
end.