记录编号	189767	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	VacaTionGOD	是否通过	通过
代码语言	Pascal	运行时间	1.010 s
提交时间	2015-09-29 13:31:58	内存使用	8.76 MiB

var
  i,j,k,n,ans,min:longint;
  f:array[1..1500] of boolean;
  d:array[1..1500] of longint;
  a:array[1..1500,1..1500] of longint;
procedure Prim;
begin
  for i:=1 to n do begin d[i]:=a[1,i]; f[i]:=false; end;
  f[1]:=true;
  ans:=0;
  for i:=2 to n do
    begin
      min:=maxlongint div 2;
      for j:=1 to n do
       if (not f[j]) and (d[j]<min) then
         begin min:=d[j]; k:=j; end;
       inc(ans,d[k]);
       f[k]:=true;
      for j:=1 to n do
       if (not f[j]) and (a[k,j]<d[j]) then d[j]:=a[k,j];
    end;
end;
begin
assign(input,'wire.in');
reset(input);
assign(output,'wire.out');
rewrite(output);
  readln(n);
  for i:=1 to n do  begin
   for j:=1 to n do
    read(a[i,j]); readln; end;
  Prim;
  writeln(ans);
close(input);
close(output);
end.