CHEER - Động viên đàn bò
Tác giả: ll931110
Ngôn ngữ: Pascal
program CHEER;
const
input = '';
output = '';
maxn = 10000;
maxp = 100000;
type
edge = record
u,v,cost: longint;
end;
var
e: array[1..maxp] of edge;
a,pr,rank: array[1..maxn] of longint;
n,p: longint;
res: longint;
procedure init;
var
f: text;
i: longint;
begin
assign(f, input);
reset(f);
readln(f, n, p);
for i := 1 to n do read(f, a[i]);
for i := 1 to p do
begin
read(f, e[i].u, e[i].v, e[i].cost);
e[i].cost := 2 * e[i].cost + a[e[i].u] + a[e[i].v];
end;
close(f);
end;
procedure swap(var x,y: edge);
var
z: edge;
begin
z := x; x := y; y := z;
end;
procedure sort(l,h: longint);
var
i,j: longint;
t: longint;
begin
if l >= h then exit;
i := l; j := h; t := e[random(h - l + 1) + l].cost;
repeat
while e[i].cost < t do inc(i);
while e[j].cost > t do dec(j);
if i <= j then
begin
if i < j then swap(e[i],e[j]);
inc(i);
dec(j);
end;
until i > j;
sort(l,j); sort(i,h);
end;
procedure makeset(i: longint);
begin
pr[i] := i;
rank[i] := 0;
end;
function root(x: longint): longint;
begin
if x <> pr[x] then pr[x] := root(pr[x]);
root := pr[x];
end;
procedure link(x,y: longint);
begin
if rank[x] > rank[y] then pr[y] := x else pr[x] := y;
if rank[x] = rank[y] then inc(rank[y]);
end;
procedure union(x,y: longint);
begin
link(root(x),root(y));
end;
procedure Kruskal;
var
i,cc: longint;
begin
cc := 0;
res := 0;
for i := 1 to n do
if (res = 0) or (res > a[i]) then res := a[i];
for i := 1 to n do makeset(i);
for i := 1 to p do
begin
if cc = n - 1 then break;
if root(e[i].u) <> root(e[i].v) then
begin
res := res + e[i].cost;
union(e[i].u,e[i].v);
inc(cc);
end;
end;
end;
procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, res);
close(f);
end;
begin
init;
sort(1,p);
Kruskal;
printresult;
end.