jiry_2's Blog

水题，加一个点最小生成树

program p01;
    var
        b:array[0..300,0..300] of longint;
        d:array[0..300] of longint;
        n,i,j,tot:longint;
    function findmin:longint;
        var
            i,j,k:longint;
        begin
            j:=0; k:=maxlongint;
            for i:=0 to n do
                if (k>d[i]) and (d[i]<>-1) then begin
                    j:=i; k:=d[i];
                end;
            exit(j);
        end;
    procedure change(k:longint);
        var
            i,j:longint;
        begin
            for i:=0 to n do
                if b[k,i]<d[i] then d[i]:=b[k,i];
            d[k]:=-1;
        end;
    begin
        readln(n);
        for i:=1 to n do begin
            read(b[0,i]);
            b[i,0]:=b[0,i];
        end;
        for i:=1 to n do
            for j:=1 to n do
                read(b[i,j]);
        fillchar(d,sizeof(d),$3f);
        d[0]:=0; tot:=0;
        for i:=0 to n do begin
            j:=findmin;
            tot:=tot+d[j];
            change(j);
        end;
        writeln(tot);
    end.