2292 - L2126 的题解

回去原题
#的最小生成树,附上prim标程:
var
  n,m,i,j,k,c,d,e:longint;
  a,b:array [0..10000] of longint;
  f:array [0..2300,0..2300] of longint;
  dis:array [0..10000] of longint;
  min,sum:longint;
  used:array [0..10000] of boolean;
begin
  assign(input,'mzcanddjn.in');
  reset(input);
  assign(output,'mzcanddjn.out');
  rewrite(output);
  readln(n);
  readln(m);
  fillchar(f,sizeof(f),$7f);
  for i:=1 to m do
    begin
      readln(c,d,e);
      f[c,d]:=e;
      f[d,c]:=e;
    end;
  fillchar(dis,sizeof(dis),$7f);
  dis[0]:=0;
  sum:=0;
  for i:=0 to n do
    begin
      min:=maxlongint;
      for j:=0 to n do
        if not used[j] and (dis[j]<min) then
          begin
            k:=j;
            min:=dis[j];
          end;
      used[k]:=true;
      sum:=sum+dis[k];
      for j:=1 to n do
        if not used[j] and (f[k,j]<dis[j]) then
          dis[j]:=f[k,j];
    end;
  writeln(sum);
  close(input);
  close(output);
end.