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.