CHEER - Động viên đàn bò

Tác giả: RR

Ngôn ngữ: Pascal

{
PROG: cheer
LANG: PASCAL
ID: invinci3
}
const
  FINP='';
  FOUT='';
  MAXN=10011;
  MAXM=100011;
var
  cost,father:array[1..MAXN] of longint;
  eu,ev,ec:array[1..MAXM] of longint;
  kq,n,m:longint;
procedure inp;
var
  f:text;
  i,u,v,c:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  kq:=maxlongint;
  for i:=1 to n do
    begin
      read(f,cost[i]);
      if kq>cost[i] then kq:=cost[i];
    end;
  for i:=1 to m do
    begin
      read(f,u,v,c);
      eu[i]:=u; ev[i]:=v;
      ec[i]:=2*c+cost[u]+cost[v];
    end;
  close(f);
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint); inline;
var
  i,j,mid:longint;
begin
  i:=l; j:=r; mid:=ec[l+random(r-l+1)];
  repeat
    while ec[i]<mid do inc(i);
    while ec[j]>mid do dec(j);
    if i<=j then
      begin
        swap(eu[i],eu[j]);
        swap(ev[i],ev[j]);
        swap(ec[i],ec[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
function getRoot(u:longint):longint;
begin
  if father[u]<0 then getRoot:=u
  else begin father[u]:=getRoot(father[u]); getRoot:=father[u]; end;
end;
procedure union(r1,r2:longint);
var
  x:longint;
begin
  x:=father[r1]+father[r2];
  if father[r1]<father[r2] then
    begin
      father[r1]:=x;
      father[r2]:=r1;
    end
  else
    begin
      father[r2]:=x;
      father[r1]:=r2;
    end;
end;
procedure solve;
var
  i,count,r1,r2:longint;
begin
  for i:=1 to n do father[i]:=-1;
  count:=0;
  for i:=1 to m do
    begin
      r1:=getRoot(eu[i]); r2:=getRoot(ev[i]);
      if r1=r2 then continue;
      inc(count); inc(kq,ec[i]);
      if count=n-1 then break;
      union(r1,r2);
    end;
end;
begin
  inp;
  sort(1,m);
  solve;
  ans;
end.

Download