HAF1 - Đua Xe
Tác giả: RR
Ngôn ngữ: Pascal
{$R-,Q-}
uses math;
const
FINP='';
FOUT='';
MAXN=1000;
var
n,m:longint;
f1,f2:text;
left,right,a:array[1..MAXN,1..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i,j:longint;
begin
read(f1,n,m);
for i:=1 to m do
for j:=1 to n do
read(f1,a[i,j]);
end;
procedure ans;
var
luu,j:longint;
begin
luu:=maxlongint;
for j:=1 to n do
luu:=min(min(left[m,j],right[m,j]),luu);
writeln(f2,luu);
end;
procedure solve;
var
i,j:longint;
begin
for j:=1 to n do
begin
left[1,j]:=a[1,j];
right[1,j]:=a[1,j];
end;
for i:=2 to m do
begin
for j:=1 to n do
begin
left[i,j]:=min(left[i-1,j],right[i-1,j])+a[i,j];
right[i,j]:=left[i,j];
end;
for j:=2 to n do
right[i,j]:=min(right[i,j],right[i,j-1]+a[i,j]);
for j:=n-1 downto 1 do
left[i,j]:=min(left[i,j],left[i,j+1]+a[i,j]);
end;
end;
begin
openF;
inp;
solve;
ans;
closeF;
end.