HAF1 - Đua Xe

Tác giả: flashmt

Ngôn ngữ: Pascal

const maxn=1111;
      max=1000000000;
var m,n,re:longint;
    a:array[1..maxn,1..maxn] of longint;
    d,r,l:array[1..maxn] of longint;

procedure rf;
var i,j:longint;
begin
     readln(n,m);
     for i:=1 to m do
         for j:=1 to n do
             read(a[i,j]);
end;

function min(a,b:longint):longint;
begin
     if (a<=b) then min:=a else min:=b;
end;

procedure pr;
var i,j:longint;
begin
     fillchar(d,sizeof(d),0);
     fillchar(l,sizeof(l),0);
     fillchar(r,sizeof(r),0);
     for i:=1 to n do d[i]:=a[1,i];
     for i:=2 to m do
     begin
          r[n]:=d[n]+a[i,n];
          l[1]:=d[1]+a[i,1];
          for j:=2 to n do
              l[j]:=min(l[j-1],d[j])+a[i,j];
          for j:=n-1 downto 1 do
              r[j]:=min(r[j+1],d[j])+a[i,j];
          for j:=1 to n do
              d[j]:=min(l[j],r[j]);
     end;
     re:=max;
     for j:=1 to n do
         if d[j]<re then re:=d[j];
end;

procedure wf;
begin
     write(re);
end;

begin
     rf;
     pr;
     wf;
end.

Download