记录编号	39428	评测结果	AAAAA
题目名称	RCDH外星人	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.173 s
提交时间	2012-07-10 20:55:46	内存使用	4.23 MiB

program et;
const maxn=30000; maxr=11; maxm=5*maxn;
var
 n,m,i,j,x,y,ans,z,k,l,tot:longint;
 a:array[0..maxr,0..maxn] of longint;
 aa,dis,temp:array[0..maxn] of longint;
 next,link,c,f:array[0..maxm] of longint;
 v,vv:array[0..maxn] of boolean;
 procedure spfa(k:longint);
 var i,h,t:longint;
 begin
  h:=0; t:=1; f[1]:=k; v[k]:=true; dis[k]:=0;
  repeat
   inc(h);
   v[f[h]]:=false;
   i:=aa[f[h]];
   while i<>0 do
    begin
     if dis[f[h]]+c[i]<dis[link[i]] then
      begin
       dis[link[i]]:=dis[f[h]]+c[i];
       if not vv[link[i]] then
        begin
         ans:=ans+1;
         vv[link[i]]:=true;
        end;
        if not v[link[i]] then
         begin
          v[link[i]]:=true;
          inc(t);
          f[t]:=link[i];
         end;
      end;
     i:=next[i];
    end;
  until h=t;
 end;
 procedure spfa2(k:Longint);
 var i,h,t:longint;
 begin
  h:=0; t:=0;
  for i:=1 to a[k,0] do
   begin
    inc(t); f[t]:=a[k,i]; v[a[k,i]]:=true;
    dis[a[k,i]]:=0;
   end;
  if t=0 then exit;
  repeat
   inc(h);
   v[f[h]]:=false;
   i:=aa[f[h]];
   while i<>0 do
    begin
     if dis[f[h]]+c[i]<dis[link[i]] then
      begin
       dis[link[i]]:=dis[f[h]]+c[i];
        if not v[link[i]] then
         begin
          v[link[i]]:=true;
          inc(t);
          f[t]:=link[i];
         end;
      end;
     i:=next[i];
    end;
  until h=t;
 end;
 procedure insert(x,y,z:longint);
 begin
  inc(tot); next[tot]:=aa[x]; aa[x]:=tot;
  link[tot]:=y; c[tot]:=z;
 end;
begin
 assign(input,'et.in'); reset(input);
 assign(output,'et.out'); rewrite(output);
 readln(n,m);
 for i:=1 to n do
  begin
   read(x);
   inc(a[x,0]); a[x,a[x,0]]:=i;
  end;
 for i:=1 to m do
  begin
   read(x,y,z);
   insert(x,y,z);
   insert(y,x,z);
   end;
 fillchar(dis,sizeof(dis),$7f div 2);
 temp:=dis; z:=0;
 fillchar(v,sizeof(v),#0);
 for i:=10 downto 1 do
  begin
   for j:=1 to a[i,0] do
    begin spfa(a[i,j]); dis:=temp; vv:=v; end;
   spfa2(i);
   temp:=dis;
  end;
 writeln(ans+n);
 close(input); close(output);
end.