记录编号	80798	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	gungnir	是否通过	通过
代码语言	Pascal	运行时间	1.040 s
提交时间	2013-11-07 18:04:55	内存使用	15.45 MiB

type btype=array[0..2000]of longint;
var    n,i,j,k,min,ans:longint;
       b:btype;
       a:array[0..2000,0..2000]of longint;
       f:array[0..2000]of boolean;

function check(b:btype):boolean;
var i:longint;
begin
check:=true;
for i:=1 to n do
if f[i] then begin check:=false; exit; end;
end;

begin
assign(input,'wire.in');reset(input);
assign(output,'wire.out');rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=maxlongint;

for i:=1 to n do
for j:=1 to n do
read(a[i,j]);

for i:=1 to n do f[i]:=true;
f[1]:=false;
i:=1;
ans:=0;
for j:=2 to n do b[j]:=a[1,j];

repeat
min:=maxlongint;
for j:=1 to n do
if(i<>j)and(b[j]<min)and(f[j])then  begin k:=j; min:=b[j]; end;
ans:=ans+b[k];
f[k]:=false;
for j:=1 to n do
if (i<>j)and(k<>j)and(f[j])and(a[k,j]<b[j])
then b[j]:=a[k,j];
i:=k;
until check(b);

writeln(ans);
close(input);close(output);
end.