DISNEY1 - Công viên Disneyland (version 1)

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
PROGRAM DISNEY1;
CONST
  FINP='';
  FOUT='';
  maxn=201;
  oo=1000000000;
VAR
  d,v:array[1..maxn,1..maxn] of longint;
  n:longint;
procedure readInput;
var
  i,j:longint;
  f:text;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  for i:=1 to n do
    for j:=1 to n do
      read(f,v[i,j]);
  close(f);
end;
function min(a,b:longint):longint;
begin
  if a<b then min:=a else min:=b;
end;
procedure solve;
var
  f:text;
  i,j,cost:longint;
begin
  assign(f,FOUT); rewrite(f);
  d[1,1]:=0;
  for i:=2 to n do
    begin
      d[i,i]:=oo;
      for j:=1 to i-1 do
        d[i,j]:=d[i-1,j]+v[i-1,i];
      for j:=1 to i-1 do
        begin
          d[i,i-1]:=min(d[i,i-1],d[i-1,j]+v[j,i]);
          d[i,i]:=min(d[i,i],d[i-1,j]+v[j,i]+v[i-1,i]);
        end;
    end;
  cost:=oo;
  for i:=1 to n do
    cost:=min(cost,d[n,i]+v[n,1]+v[i,1]);
  writeln(f,cost);
  close(f);
end;
BEGIN
  readInput;
  solve;
END.

Download