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.