## Editorial for VM 08 Bài 13 - Bin Laden

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
oo=1000000000;
dx:array[1..4] of longint=(-1,0,1,0);
dy:array[1..4] of longint=(0,1,0,-1);
maxm=2500;
var m,n,f,nh:longint;
ngang,doc:array[1..maxm,1..10] of longint;
pos,h,p,d,cur:array[1..maxm*10] of longint;
free:array[1..maxm*10] of boolean;
stt:array[0..maxm,1..10] of longint;
a,c:array[1..maxm*10*8] of longint;

function calc(i,j,ii,jj:longint):longint;
begin
if i=ii then
begin
if j<jj then calc:=ngang[i,j]
else calc:=ngang[i,jj];
end
else
begin
if i<ii then calc:=doc[ii,j]
else calc:=doc[i,j];
end;
end;

procedure rf;
var i,j,dem,k,x,y,ii,jj:longint;
begin
for i:=1 to m do
begin
for j:=1 to n do read(doc[i,j]);
for j:=1 to n-1 do read(ngang[i,j]);
end;
dem:=1;
for i:=1 to m do
for j:=1 to n do
begin
inc(dem);
stt[i,j]:=dem;
end;
pos[1]:=1; cur[1]:=n;
for i:=1 to n do
begin
a[i]:=stt[1,i];
c[i]:=doc[1,i];
stt[0,i]:=1;
end;
for i:=1 to m do
for j:=1 to n do
begin
x:=stt[i,j];
pos[x]:=cur[x-1]+1; cur[x]:=cur[x-1];
for k:=1 to 4 do
begin
ii:=i+dx[k]; jj:=j+dy[k];
if (ii<=m) and (jj>0) and (jj<=n) then
begin
y:=stt[ii,jj];
inc(cur[x]);
a[cur[x]]:=y;
c[cur[x]]:=calc(i,j,ii,jj);
end;
end;
end;
f:=x;
pos[f+1]:=cur[f]+1;
end;

procedure update(x:longint);
var cha,con:longint;
begin
con:=p[x];
if con=0 then
begin
inc(nh); con:=nh;
end;
cha:=con shr 1;
while (cha>0) and (d[h[cha]]>d[x]) do
begin
h[con]:=h[cha];
p[h[con]]:=con;
con:=cha;
cha:=con shr 1;
end;
h[con]:=x; p[x]:=con;
end;

function pop:longint;
var x,cha,con:longint;
begin
pop:=h[1];
x:=h[nh]; dec(nh);
cha:=1; con:=2;
while (con<=nh) do
begin
if (con<nh) and (d[h[con+1]]<d[h[con]]) then inc(con);
if d[x]<=d[h[con]] then break;
h[cha]:=h[con];
p[h[cha]]:=cha;
cha:=con;
con:=cha shl 1;
end;
h[cha]:=x; p[x]:=cha;
end;

procedure pr;
var i,x,y:longint;
begin
for i:=1 to f do
begin
free[i]:=true; d[i]:=oo;
end;
d[1]:=0;
update(1);
repeat
x:=pop; free[x]:=false;
if x=f then break;
for i:=pos[x] to pos[x+1]-1 do
begin
y:=a[i];
if free[y] and (d[y]>d[x]+c[i]) then
begin
d[y]:=d[x]+c[i];
update(y);
end;
end;
until nh=0;
writeln(d[f]);
end;

begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)
#define hash(a,b) (((a)-1)*n+(b))

#define INF 1000000000/*(int(1e9))*/
#define M 2500
#define N 20

int a[2*M][N],m,n,d[M*N];
//long long d[M*N];
vvii g;

void dijkstra() {
fill(d+1,d+m*n+1,INF);
priority_queue< ii, vii, greater<ii> > qu; qu.push(ii(0, 0));
while(!qu.empty()) {
ii top = qu.top(); qu.pop();
int du = top.fi, u = top.se;
if( du > d[u] ) continue;
tr(g[u],it) {
int v = it->fi, l = it->se;
if( d[v] > du + l ) qu.push(ii(d[v] = du + l, v));
}
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
#endif
scanf("%d%d",&m,&n);
fo(i,1,2*m) fo(j,1,n-1+i%2) scanf("%d",&a[i][j]);
g.resize(m*n+1);
fo(i,1,m) fo(j,1,n) {
int p = hash(i,j);
if(i != m) g[p].pb(ii(hash(i+1,j), a[i+i+1][j]));
if(i != 1) g[p].pb(ii(hash(i-1,j), a[i+i-1][j]));
if(j != n) g[p].pb(ii(hash(i,j+1), a[i+i][j]));
if(j != 1) g[p].pb(ii(hash(i,j-1), a[i+i][j-1]));
}
fo(i,1,n) g[0].pb(mp(i, a[1][i]));
#ifndef ONLINE_JUDGE
rep(i,m*n+1) {
printf("%d", i);
tr(g[i], it) printf(" (%d %d)", it->fi, it->se);
putchar(10);
}
#endif
dijkstra(); printf("%d\n", d[m*n]);
return 0;
}


{$MODE OBJFPC} program binladen; uses math; const maxn=11; maxm=2223; oo=trunc(1e9); up=1;r=4;down=3;l=2; dx:array[1..4] of longint = (-1,0,1,0); dy:array[1..4] of longint = (0,1,0,-1); fi=''; type e=record x,y:longint; end; var m,n,nh:longint; pos,d:array[0..maxm,1..maxn] of longint; h:array[1..maxm*maxn] of e; a:array[0..maxm,0..maxn,1..4] of longint; procedure input; var inp:text; i,j,w:longint; begin assign(inp,fi);reset(inp); readln(inp,m,n); for i:=1 to 2*m do begin if odd(i) then for j:=1 to n do begin read(inp,w); a[i div 2+1,j,up]:=w; a[i div 2,j,down]:=w; end else for j:=1 to n-1 do begin read(inp,w); a[i div 2,j,l]:=w; a[i div 2,j+1,r]:=w; end; end; close(inp); end; procedure update(u,v:longint); var p,c:longint; begin c:=pos[u,v]; if c=0 then begin inc(nh); c:=nh; end; repeat p:=c shr 1; if (p=0) or (d[h[p].x,h[p].y]<=d[u,v]) then break; h[c]:=h[p]; pos[h[c].x,h[c].y]:=c; c:=p; until false; h[c].x:=u;h[c].y:=v; pos[u,v]:=c; end; function extract:e; var p,c:longint; v:e; begin result:=h[1]; v:=h[nh]; dec(nh); p:=1; repeat c:=2*p; if (c<nh) and (d[h[c+1].x,h[c+1].y]<d[h[c].x,h[c].y]) then inc(c); if (c>nh) or (d[h[c].x,h[c].y]>=d[v.x,v.y]) then break; h[p]:=h[c]; pos[h[p].x,h[p].y]:=p; p:=c; until false; h[p]:=v; pos[v.x,v.y]:=p; end; procedure dijkstra; var i,j,x,y,w:longint; u:e; begin for i:=1 to m do for j:=1 to n do d[i,j]:=oo; for j:=1 to n do update(0,j); repeat u:=extract; for i:=1 to 4 do begin x:=u.x+dx[i]; y:=u.y+dy[i]; if (x<1) or (y<1) or (x>m) or (y>n) then continue; w:=a[u.x,u.y,i]; if d[x,y]>d[u.x,u.y]+w then begin d[x,y]:=d[u.x,u.y]+w; update(x,y); end; end; until nh=0; end; begin input; dijkstra; write(d[m,n]); end.  #### Code mẫu của RR {$R+,Q+}
const
FINP='';
FOUT='';
MAXN=20;
MAXM=3000;
oo=100000000;
var
m,n,hsize:longint;
hpos,d:array[1..MAXM,1..MAXN] of longint;
hu,hv:array[1..MAXN*MAXM] of longint;
cx,cs:array[1..MAXM,1..MAXN] of longint;
procedure inp;
var
i,j:longint;
begin
assign(input,FINP); reset(input);
for i:=1 to m do
begin
for j:=1 to n do read(cx[i,j]);
for j:=2 to n do read(cs[i,j]);
end;
close(input);
end;
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
j:longint;
begin
j:=i shl 1;
while (j<=hsize) do
begin
if (j<hsize) and (d[hu[j+1],hv[j+1]]<d[hu[j],hv[j]]) then inc(j);
if d[hu[j],hv[j]]<d[hu[i],hv[i]] then
begin
swap(hpos[hu[j],hv[j]],hpos[hu[i],hv[i]]);
swap(hu[i],hu[j]);
swap(hv[i],hv[j]);
end;
i:=j; j:=i shl 1;
end;
end;
procedure upHeap(i:longint);
var
j:longint;
begin
j:=i shr 1;
while (i>1) and (d[hu[j],hv[j]]>d[hu[i],hv[i]]) do
begin
swap(hpos[hu[i],hv[i]],hpos[hu[j],hv[j]]);
swap(hu[i],hu[j]);
swap(hv[i],hv[j]);
i:=j; j:=i shr 1;
end;
end;
procedure push(u,v:longint);
begin
inc(hsize);
hu[hsize]:=u; hv[hsize]:=v;
hpos[u,v]:=hsize;
upHeap(hsize);
end;
procedure pop(var u,v:longint);
begin
u:=hu[1]; v:=hv[1];
swap(hpos[hu[1],hv[1]],hpos[hu[hsize],hv[hsize]]);
swap(hu[1],hu[hsize]);
swap(hv[1],hv[hsize]);
dec(hsize);
downHeap(1);
end;
procedure solve;
var
u,v,i:longint;
begin
hsize:=0;
for u:=1 to m do
for v:=1 to n do
d[u,v]:=oo;
for i:=1 to n do
begin
d[1,i]:=cx[1,i];
push(1,i);
end;
while hsize>0 do
begin
pop(u,v);
if (u=m) and (v=n) then
begin
assign(output,FOUT); rewrite(output);
writeln(d[u,v]);
close(output);
halt;
end;
if (u<m) and (d[u+1,v]>d[u,v]+cx[u+1,v]) then
begin
d[u+1,v]:=d[u,v]+cx[u+1,v];
if hpos[u+1,v]=0 then push(u+1,v)
else upHeap(hpos[u+1,v]);
end;
if (u>1) and (d[u-1,v]>d[u,v]+cx[u,v]) then
begin
d[u-1,v]:=d[u,v]+cx[u,v];
if hpos[u-1,v]=0 then push(u-1,v)
else upHeap(hpos[u-1,v]);
end;
if (v>1) and (d[u,v-1]>d[u,v]+cs[u,v]) then
begin
d[u,v-1]:=d[u,v]+cs[u,v];
if hpos[u,v-1]=0 then push(u,v-1)
else upHeap(hpos[u,v-1]);
end;
if (v<n) and (d[u,v+1]>d[u,v]+cs[u,v+1]) then
begin
d[u,v+1]:=d[u,v]+cs[u,v+1];
if hpos[u,v+1]=0 then push(u,v+1)
else upHeap(hpos[u,v+1]);
end;
end;
end;
begin
inp;
solve;
end.


#### Code mẫu của ll931110

{\$MODE DELPHI}
Const
input  = '';
output = '';
maxm = 2500;
maxn = 12;
maxv = 100000000;
maxk = 25000;
Type
rec = record
x,y: integer;
end;
Var
d,a,c,pos: array[0..maxm,0..maxn] of integer;
heap: array[1..maxk] of rec;
free: array[0..maxm,0..maxn] of boolean;
m,n: integer;
p,q: integer;
nHeap: integer;

Procedure init;
Var
f: text;
i,j: integer;
Begin
Assign(f, input);
Reset(f);

For i:= 0 to maxm do
For j:= 0 to maxn do
Begin
a[i,j]:= maxv;
c[i,j]:= maxv;
End;

For i:= 1 to m do
Begin
For j:= 1 to n do read(f, a[i,j]);
For j:= 1 to n - 1 do read(f, c[i,j]);
End;

Close(f);
End;

Procedure update(u,v: integer);
Var
ch,pr: integer;
Begin
ch:= pos[u,v];
If ch = 0 then
Begin
inc(nHeap);
ch:= nHeap;
End;

pr:= ch div 2;
While (pr > 0) and
(d[heap[pr].x,heap[pr].y] > d[u,v]) do
Begin
heap[ch]:= heap[pr];
pos[heap[ch].x,heap[ch].y]:= ch;

ch:= pr;
pr:= ch div 2;
End;

heap[ch].x:= u;
heap[ch].y:= v;
pos[u,v]:= ch;
End;

Procedure pop;
Var
u,v,r,k: integer;
Begin
p:= heap[1].x;
q:= heap[1].y;

u:= heap[nHeap].x;
v:= heap[nHeap].y;
dec(nHeap);

r:= 1;
While r * 2 <= nHeap do
Begin
k:= r * 2;
If (k < nHeap) and
(d[heap[k + 1].x,heap[k + 1].y] < d[heap[k].x,heap[k].y]) then inc(k);

If d[heap[k].x,heap[k].y] >= d[u,v] then break;

heap[r]:= heap[k];
pos[heap[r].x,heap[r].y]:= r;
r:= k;
End;

heap[r].x:= u;
heap[r].y:= v;
pos[u,v]:= r;
End;

Procedure Dijkstra;
Var
i,j: integer;
Begin
Fillchar(free, sizeof(free), false);
For i:= 1 to m do
For j:= 1 to n do free[i,j]:= true;

Fillchar(pos, sizeof(pos), 0);
nHeap:= 0;

For i:= 0 to maxm do
For j:= 0 to maxn do d[i,j]:= maxv;

For i:= 1 to n do
Begin
d[1,i]:= a[1,i];
update(1,i);
End;

Repeat
pop;
If (p = m) and (q = n) then break;

free[p,q]:= false;
If free[p + 1,q] and (d[p + 1,q] > d[p,q] + a[p + 1,q]) then
Begin
d[p + 1,q]:= d[p,q] + a[p + 1,q];
update(p + 1,q);
End;

If free[p - 1,q] and (d[p - 1,q] > d[p,q] + a[p,q]) then
Begin
d[p - 1,q]:= d[p,q] + a[p,q];
update(p - 1,q);
End;

If free[p,q + 1] and (d[p,q + 1] > d[p,q] + c[p,q]) then
Begin
d[p,q + 1]:= d[p,q] + c[p,q];
update(p,q + 1);
End;

If free[p,q - 1] and (d[p,q - 1] > d[p,q] + c[p,q - 1]) then
Begin
d[p,q - 1]:= d[p,q] + c[p,q - 1];
update(p,q - 1);
End;
Until nHeap = 0;
End;

Procedure printresult;
Var
f: text;
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, d[m,n]);
Close(f);
End;

Begin
init;
Dijkstra;
printresult;
End.