TTRIP - Tham quan Thành Cổ

Tác giả: ladpro98

Ngôn ngữ: Pascal

program TTRIP;
uses    math;
const   maxn=101;
        fi='';
        oo=trunc(1e9);
var     a:array[1..maxn,1..maxn] of longint;
        chk:array[1..maxn] of boolean;
        n:longint;

procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do
        for j:=1 to n do begin
                read(inp,a[i,j]);
                if a[i,j]=0 then a[i,j]:=oo;
        end;
        close(inp);
end;

procedure floyd;
var     i,j,k:longint;
begin
        for k:=1 to n do
        for i:=1 to n do
        for j:=1 to n do
        a[i,j]:=min(a[i,j],a[i,k]+a[k,j]);
end;

procedure process;
var     res,s,i,j,m,minw:longint;

begin
        s:=1;res:=0;
        for i:=2 to n-1 do begin
                minw:=oo;m:=0;
                for j:=2 to n-1 do
                if (not chk[j]) and (a[s,j]<minw) then begin
                        m:=j;
                        minw:=a[s,j];
                end;
                if minw=oo then break;
                inc(res,minw);
                chk[m]:=true;
                s:=m;
        end;
        write(res+a[s,n]);
end;

begin
        input;
        floyd;
        process;
end.

Download