DISNEY2 - Công viên Disneyland (version 2)
Tác giả: RR
Ngôn ngữ: Pascal
program DISNEY2;
const
FINP='';
FOUT='';
MAXN=202;
oo= maxlongint div 2;
var
d,c:array[1..MAXN,1..MAXN] of longint;
n:integer;
procedure inp;
var
f:text;
i,j:integer;
begin
assign(f,FINP); reset(f);
readln(f,n);
for i:=1 to n do
for j:=1 to n do
read(f,c[i,j]);
close(f);
for i:=2 to n do
c[i,n+1]:=c[1,i];
end;
procedure ans;
var
f:text;i,j:longint;
begin
assign(f,FOUT); rewrite(f);
writeln(f,d[n+1,n+1]);
close(f);
end;
function min(a,b:longint):longint;
begin
if a<b then min:=a else min:=b;
end;
procedure solve;
var
i,j:integer;
begin
for i:=1 to n+1 do
for j:=1 to n+1 do
d[i,j]:=oo;
d[1,1]:=0;
d[2,1]:=c[1,2];
d[1,2]:=c[1,2];
for i:=3 to n+1 do
begin
for j:=1 to i-2 do d[i,j]:=d[i-1,j]+c[i-1,i];
for j:=1 to i-2 do
d[i,i-1]:=min(d[i,i-1],d[i-1,j]+c[j,i]);
end;
for i:=1 to n do
d[n+1,n+1]:=min(d[n+1,n+1],d[n+1,i]+d[i,n+1]);
for i:=1 to n-1 do
d[n+1,n+1]:=min(d[n+1,n+1],d[n,i]+c[n,n+1]+c[i,n+1]);
end;
begin
inp;
solve;
ans;
end.