记录编号	14220	评测结果	AAAAA
题目名称	[NOI 1998]SERNET模拟	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	Pascal	运行时间	0.011 s
提交时间	2009-10-28 08:51:35	内存使用	0.24 MiB

program xmz;
var
f1,f2:text;
d,f:array[1..100,1..100]of longint;
y:array[1..100,1..100]of boolean;
long,bh:array[1..100]of longint;
ml:array[1..10000]of longint;
a,b,q,z,t1,t2,t3,n,bn,time,s:longint;
procedure djs;
 var
 i,k,min:longint;
 begin
  fillchar(y[q],sizeof(y[q]),false);
  for i:=1 to n do d[q,i]:=99999999;
  k:=q;d[q,k]:=time;
  repeat
   y[q,k]:=true;
   if k<>z then
   for i:=1 to n do
    if (f[k,i]<>0)and(f[k,i]+d[q,k]<d[q,i])and(not y[q,i]) then
    d[q,i]:=f[k,i]+d[q,k];
    min:=99999999;
   for i:=1 to n do
    if (d[q,i]<min)and(not y[q,i]) then begin min:=d[q,i];k:=i;end;
  until min=99999999;
 end;
begin
 assign(f1,'sernet.in');assign(f2,'sernet.out');
 reset(f1);rewrite(f2);
  read(f1,n);
  for a:=1 to n do
   begin read(f1,t1);bh[t1]:=a;end;
  read(f1,bn);
  for a:=1 to bn do
   begin
    read(f1,t1,t2,t3);
    t1:=bh[t1];
    t2:=bh[t2];
    f[t1,t2]:=t3;
    f[t2,t1]:=t3;
   end;
  read(f1,bn);

  for a:=1 to n do
   for b:=1 to n do
    if (f[a,b]<>0)and(f[a,b]>long[a])then long[a]:=f[a,b];

  for a:=1 to bn do
   begin
    read(f1,t1);
    read(f1,time,q,z);
    q:=bh[q];z:=bh[z];
    djs;
    for b:=1 to n do
     if (b<>z)and(d[q,b]<>99999999) then inc(d[q,b],long[b]);
    for b:=1 to n do
     if (d[q,b]>ml[a])and(d[q,b]<99999999) then ml[a]:=d[q,b];
   end;
  read(f1,t1);
  for a:=1 to bn  do
   if ml[a]>t1 then inc(s);
  writeln(f2,s);
 close(f1);close(f2);
end.