k.i.d 2010-11-16 23:09:00
点我顶贴
收藏
删除
const oo=100000000;
var
cost:array[0..1001,0..1001] of longint;
mincost:array[0..1001] of longint;
n,m,i,j,k,x,y,a,min,ans:longint;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y,a);
if (cost[x,y]>a)or(cost[x,y]=0) then
begin
cost[x,y]:=a;
cost[y,x]:=a;
end;
end;
for i:=1 to n do
for j:=1 to n do
if (i<>j)and(cost[i,j]=0) then cost[i,j]:=oo;
for i:=1 to n do
mincost[i]:=cost[1,i];
for i:=2 to n do
begin
min:=oo;
for j:=1 to n do
if (mincost[j]<min)and(mincost[j]<>0) then
begin
k:=j;
min:=mincost[j];
end;
inc(ans,mincost[k]);
mincost[k]:=0;
for j:=1 to n do
if (mincost[j]>cost[k,j])and(mincost[j]<>0) then
mincost[j]:=cost[k,j];
end;
writeln(ans);
end.