记录编号	23790	评测结果	AAAA
题目名称	服务器储存信息问题	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	1.182 s
提交时间	2011-03-21 09:55:24	内存使用	3.72 MiB

{服务器储存信息问题
 最短路径
 Author: yangbohua
 Time: 2011-03-21}

program servers;
type
  bian=record
    v,w,next:longint;
  end;

var
  map:array[0..150000] of bian;
  list:array[0..30000] of longint;
  dist:array[0..30000,0..11] of longint;
  best,q,r:array[0..30000] of longint;
  b,js:array[0..30000] of boolean;
  n,m,i,j,num,maxr,r1,r2,r3,h,t,u,ans:longint;

begin
  assign(input,'servers.in');
  reset(input);
  assign(output,'servers.out');
  rewrite(output);

  readln(n,m);
  maxr:=0;
  for i:=1 to n do
  begin
    readln(r[i]);
    if r[i]>maxr then maxr:=r[i];
  end;

  for i:=1 to m do
  begin
    readln(r1,r2,r3);
    inc(num);
    map[num].v:=r2;
    map[num].w:=r3;
    map[num].next:=list[r1];
    list[r1]:=num;

    inc(num);
    map[num].v:=r1;
    map[num].w:=r3;
    map[num].next:=list[r2];
    list[r2]:=num;
  end;

  for i:=1 to maxr do
  begin
    h:=0;
    t:=0;
    fillchar(b,sizeof(b),false);
    for j:=1 to n do
      if r[j]=i then
      begin
        t:=t+1;
        q[t]:=j;
        dist[j,i]:=0;
        b[j]:=true;
      end
      else dist[j,i]:=maxlongint;

    while h<>t do
    begin
      h:=(h mod n)+1;
      u:=list[q[h]];
      while u<>0 do
      begin
        if dist[q[h],i]+map[u].w<dist[map[u].v,i] then
        begin
          dist[map[u].v,i]:=dist[q[h],i]+map[u].w;
          if not b[map[u].v] then
          begin
            t:=(t mod n)+1;
            q[t]:=map[u].v;
            b[map[u].v]:=true;
          end;
        end;
        u:=map[u].next;
      end;
      b[q[h]]:=false;
    end;
  end;

  {for i:=1 to n do
  begin
    for j:=1 to maxr do
      write(dist[i,j],' ');
    writeln;
  end;}

  for i:=1 to n do
    for j:=maxr-1 downto 1 do
      if dist[i,j+1]<dist[i,j]
        then dist[i,j]:=dist[i,j+1];

  ans:=0;
  for i:=1 to n do
  begin
    h:=0;
    t:=1;
    q[t]:=i;
    fillchar(b,sizeof(b),false);
    fillchar(js,sizeof(js),false);
    fillchar(best,sizeof(best),$FF);
    for j:=1 to n do
      best[j]:=maxlongint;
    best[i]:=0;
    b[i]:=true;
    while h<>t do
    begin
      h:=(h mod n)+1;
      u:=list[q[h]];
      if js[q[h]]=false then
      begin
        js[q[h]]:=true;
        ans:=ans+1;
      end;
      while u<>0 do
      begin
        if (best[q[h]]+map[u].w<best[map[u].v]) or (best[map[u].v]=-1) then
        begin
          best[map[u].v]:=best[q[h]]+map[u].w;
          if (not b[map[u].v]) and (r[map[u].v]<=r[i]) and
          ((best[map[u].v]<dist[map[u].v,r[i]+1]) or (r[i]=maxr)) then
          begin
            t:=(t mod n)+1;
            q[t]:=map[u].v;
            b[map[u].v]:=true;
          end;
        end;
        u:=map[u].next;
      end;
      b[q[h]]:=false;
    end;
    {for j:=1 to n do
      if js[j] then write(j,' ');
    writeln;}
  end;

  writeln(ans);
  close(input);
  close(output);
end.