butter.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 119 行

{
ID:maigoak1
PROG:butter
}

program butter;
const
  maxn=500;
  maxp=800;
  maxc=1450;
var
  fin,fout:text;
  cow:array[1..maxp]of word;
  last:array[1..maxp]of word;
  edge:array[1..maxc*2]of record pre,vtx:word;len:byte;end;
  dist:array[1..maxp]of longint;
  heap:array[1..maxp]of word;
  pos:array[1..maxp]of integer;
  n,p,c,i,x,y,z,h,ans:longint;
procedure swap(var a:word;b:word);
  var
    t:word;
  begin
    pos[heap[a]]:=b;pos[heap[b]]:=a;
    t:=heap[a];heap[a]:=heap[b];heap[b]:=t;
    a:=b;
  end;
procedure up(p:word);
  begin
    while p>1 do
      if dist[heap[p]]<dist[heap[p shr 1]] then swap(p,p shr 1) else exit;
  end;
procedure down(p:word);
  var
    l,r:word;
  begin
    repeat
      l:=p*2;r:=l+1;
      if l>h then exit;
      if l=h then
        if dist[heap[p]]>dist[heap[l]] then swap(p,l) else exit
      else
        if (dist[heap[p]]>dist[heap[l]]) and (dist[heap[l]]<dist[heap[r]]) then
          swap(p,l)
        else if (dist[heap[p]]>dist[heap[r]]) then
          swap(p,r)
        else
          exit;
    until false;
  end;
procedure pop(var x:word);
  begin
    x:=heap[1];
    pos[x]:=-1;
    heap[1]:=heap[h];
    dec(h);
    down(1);
  end;
procedure ins(v:word;d:longint);
  begin
    dist[v]:=d;
    inc(h);
    pos[v]:=h;
    heap[h]:=v;
    up(h);
  end;
procedure dijkstra(s:word);
  var
    remain,sum,p,v,d:longint;
  begin
    remain:=n;sum:=0;h:=0;
    fillchar(pos,sizeof(pos),0);
    ins(s,0);
    repeat
      pop(s);
      dec(remain,cow[s]);inc(sum,dist[s]*cow[s]);
      if remain=0 then break;
      p:=last[s];
      while p>0 do begin
        v:=edge[p].vtx;d:=dist[s]+edge[p].len;
        if pos[v]=0 then
          ins(v,d)
        else if pos[v]>0 then
          if d<dist[v] then begin
            dist[v]:=d;
            up(pos[v]);
          end;
        p:=edge[p].pre;
      end;
    until false;
    if sum<ans then ans:=sum;
  end;
begin
  fillchar(cow,sizeof(cow),0);
  fillchar(last,sizeof(last),0);
  assign(fin,'butter.in');
  reset(fin);
  read(fin,n,p,c);
  for i:=1 to n do begin
    read(fin,x);
    inc(cow[x]);
  end;
  for i:=1 to c do begin
    read(fin,x,y,z);
    with edge[i*2-1] do begin pre:=last[x];vtx:=y;len:=z;end;last[x]:=i*2-1;
    with edge[i*2] do begin pre:=last[y];vtx:=x;len:=z;end;last[y]:=i*2;
  end;
  close(fin);

  ans:=maxlongint;
  for i:=1 to p do
    dijkstra(i);

  assign(fout,'butter.out');
  rewrite(fout);
  writeln(fout,ans);
  close(fout);
end.