ac1163.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1163;
const
  maxn=100000;
  maxm=1000000;
type
  ncard=array[0..maxn]of cardinal;
  mcard=array[1..maxm]of cardinal;
var
  price,last1,last2,dist1,dist2,h1,h2,hp1,hp2:ncard;
  v1,v2,len,pre1,pre2:mcard;
  n,m,i,ans:cardinal;
  flag1,flag2:boolean;
procedure go(var flag:boolean;
             var ver,pre:mcard;
             var last,dist,h,hp:ncard);
  var
    src,tar,t:cardinal;
  procedure pop;
    var
      d,p,l,r:cardinal;
    begin
      src:=h[1];d:=dist[h[h[0]]];p:=1;
      repeat
        l:=p*2;r:=l+1;
        if (r<h[0]) and (d>dist[h[r]]) and (dist[h[r]]<dist[h[l]]) then begin
          h[p]:=h[r];hp[h[p]]:=p;p:=r;
        end
        else if (l<h[0]) and (d>dist[h[l]]) then begin
          h[p]:=h[l];hp[h[p]]:=p;p:=l;
        end
        else
          break;
      until false;
      h[p]:=h[h[0]];hp[h[p]]:=p;dec(h[0]);
      if h[0]=0 then flag:=false;
    end;
  procedure up(v:cardinal);
    var
      d,p,f:cardinal;
    begin
      d:=dist[v];p:=hp[v];
      while p>1 do begin
        f:=p shr 1;
        if d<dist[h[f]] then begin
          h[p]:=h[f];hp[h[p]]:=p;p:=f;
        end
        else
          break;
      end;
      h[p]:=v;hp[v]:=p;
    end;
  begin
    if not flag then exit;
    pop;
    if dist[src]>=ans then begin flag:=false;exit;end;
    t:=dist1[src]+dist2[src]+price[src];if t<ans then ans:=t;
    while last[src]<>0 do begin
      tar:=ver[last[src]];
      t:=dist[src]+len[last[src]];
      if t<dist[tar] then begin
        dist[tar]:=t;up(tar);
      end;
      last[src]:=pre[last[src]];
    end;
  end;
begin
  repeat
    read(n);for i:=1 to n do begin read(m);price[i]:=m shr 1;end;
    read(m);for i:=1 to m do read(v1[i],v2[i],len[i]);

    {Create edge linklist}
    for i:=1 to n do begin last1[i]:=0;last2[i]:=0;end;
    for i:=1 to m do begin
      pre1[i]:=last1[v1[i]];last1[v1[i]]:=i;
      pre2[i]:=last2[v2[i]];last2[v2[i]]:=i;
    end;

    {Init heap}
    h1[0]:=n;h2[0]:=n;
    for i:=1 to n do begin
      dist1[i]:=maxlongint;dist2[i]:=maxlongint;
      h1[i]:=i;h2[i]:=i;hp1[i]:=i;hp2[i]:=i;
    end;
    dist1[1]:=0;dist2[1]:=0;

    {Dijkstra}
    ans:=maxlongint;flag1:=true;flag2:=true;
    repeat
      go(flag1,v2,pre1,last1,dist1,h1,hp1);
      go(flag2,v1,pre2,last2,dist2,h2,hp2);
    until not flag1 and not flag2;

    writeln(ans);
  until seekeof;
end.