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.

Download