agrinet.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:agrinet
}

program agrinet;
const
  maxn=100;
var
  fin,fout:text;
  cost:array[1..maxn,1..maxn]of longint;
  dist:array[1..maxn]of longint;
  s:set of 1..maxn;
  n,i,j,newadd:byte;
  min,total:longint;
begin
  assign(fin,'agrinet.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do
    for j:=1 to n do
      read(fin,cost[i,j]);
  close(fin);

  total:=0;
  newadd:=1;
  s:=[1];
  dist[1]:=0;
  for i:=2 to n do
    dist[i]:=maxlongint;
  for i:=2 to n do begin
    for j:=1 to n do
      if cost[newadd,j]<dist[j] then dist[j]:=cost[newadd,j];
    min:=maxlongint;
    for j:=1 to n do
      if not (j in s) then
        if dist[j]<min then begin
          min:=dist[j];
          newadd:=j;
        end;
    s:=s+[newadd];
    total:=total+min;
  end;

  assign(fout,'agrinet.out');
  rewrite(fout);
  writeln(fout,total);
  close(fout);
end.