Hướng dẫn giải của VM 08 Bài 13 - Bin Laden
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 read(m,n); 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; }
Code mẫu của ladpro98
{$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); readln(m,n); 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} Program BINLADEN; 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; Readln(f, m, n); 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.
Bình luận