TYVJ1659 (Pascal)

tyvj1659.pas

type
  edge=record
          src,dest,v:longint;
       end;

var
  a:array [0..100010] of edge;
  b,f:array [0..10000] of longint;
  ans,min,i,g,n,m:longint;

procedure swap(var p,q:edge);
var
  t:edge;

begin
  t:=p;
  p:=q;
  q:=t;
end;

procedure qsort(l,r:longint);
var
  i,j,m:longint;

begin
  i:=l;
  j:=r;
  m:=a[(l+r) shr 1].v;
  repeat
    while a[i].v<m do inc(i);
    while a[j].v>m do dec(j);
    if i<=j then
      begin
        swap(a[i],a[j]);
        inc(i);
        dec(j);
      end;
  until i>j;
  if l<j then qsort(l,j);
  if r>i then qsort(i,r);
end;

function father(p:longint):longint;
begin
  if f[p]<>p then f[p]:=father(f[p]);
  exit(f[p]);
end;

begin
  readln(n,m);
    min:=maxlongint;
  for i:=1 to n do 
    begin
      readln(b[i]);
      f[i]:=i;
      if b[i]<min then min:=b[i];
    end;
  for i:=1 to m do
    begin
      readln(a[i].src,a[i].dest,a[i].v);
      a[i].v:=a[i].v*2+b[a[i].src]+b[a[i].dest];
    end;
  qsort(1,m);
  ans:=0;
  g:=0;
  for i:=1 to m do 
    begin
      f[a[i].src]:=father(a[i].src);
      f[a[i].dest]:=father(a[i].dest);
      if f[a[i].src]<>f[a[i].dest] then
        begin
          inc(ans,a[i].v);
          f[f[a[i].src]]:=f[a[i].dest];
          inc(g);
        end;
      if g=m-1 then break;
    end;
  writeln(ans+min);
end.