Đề bài: http://vn.spoj.com/problems/DHFRBUS/
Thuật toán:
- Sử dụng thuật toán tìm đường đi ngắn nhất dijkstra.
- Gọi d[u,x] là quãng đường ngắn nhất đi từ s đến u khi dùng x vé xe miến phí
- Kết quả là d[t,k].
Code:
{$inline on} const fi =''; fo =''; maxN =trunc(1e5)*2; maxM =trunc(1e5)*10; maxK =5; oo =2*trunc(1e12); type Tadj =record v,w,link:int64; end; THeap =record v1,v2:int64; end; Arr1 =array[0..maxN] of int64; Arr2 =array[0..maxM] of Tadj; Arr4 =array[0..maxN*maxK] of THeap; Arr5 =array[0..maxN,0..maxK] of int64; var n, m, k :longint; Adj :arr2; Head :arr1; s, t :longint; d :arr5; Pos :arr5; H :arr4; nHeap :longint; c :longint; //heapmin; procedure hv(var a, b:int64); var tg :int64; begin tg:=a;a:=b;b:=tg; end; procedure UpHeap(i:longint); begin if (i<=1) or (d[H[i div 2].v1,H[i div 2].v2]<=d[H[i].v1,H[i].v2]) then exit; hv(Pos[H[i div 2].v1,H[i div 2].v2],Pos[H[i].v1,H[i].v2]); hv(H[i div 2].v1,H[i].v1); hv(H[i div 2].v2,H[i].v2); UpHeap(i div 2); end; procedure DownHeap(i:longint); var j :longint; begin j:=i*2; if j>nHeap then exit; if (j<nheap) and (d[H[j+1].v1,H[j+1].v2]<d[H[j].v1,H[j].v2]) then inc(j); if d[H[i].v1,H[i].v2]<=d[H[j].v1,H[j].v2] then exit; hv(Pos[H[i].v1,H[i].v2],Pos[H[j].v1,H[j].v2]); hv(H[i].v1,H[j].v1); hv(H[i].v2,H[j].v2); DownHeap(j); end; procedure Update(u,x:longint); var p :longint; begin p:=pos[u,x]; if p=0 then begin inc(nHeap); H[nheap].v1:=u; H[nheap].v2:=x; Pos[u,x]:=nHeap; p:=nHeap; end; UpHeap(p); end; procedure GetMin(var u, x:longint); begin if nheap=0 then begin u:=0;x:=0; exit; end; u:=H[1].v1;x:=H[1].v2; H[1].v1:=H[nHeap].v1; H[1].v2:=H[nheap].v2; Pos[H[1].v1,H[1].v2]:=1; dec(nHeap); downHeap(1); end; procedure Dijkstra; var i, v, w :int64; ans :int64; u ,x :longint; begin fillchar(pos,n,0); for u:=1 to n do for x:=0 to k do d[u,x]:=oo; nHeap:=0; d[s,0]:=0; Update(s,0); repeat GetMin(u,x); i:=head[u]; if u=0 then exit; while i<>0 do begin v:=adj[i].v; w:=adj[i].w; if d[v,x]>d[u,x]+w then begin d[v,x]:=d[u,x]+w; Update(v,x); end; if (x<k) and (d[v,x+1]>d[u,x]) then begin d[v,x+1]:=d[u,x]; Update(v,x+1); end; i:=adj[i].link; end; until nHeap=0; ans:=oo; ans:=d[t,k]; {for x:=0 to k do if d[t,x]<ans then ans:=d[t,x];} writeln(ans); end; procedure Tadd(u,v,w:longint); begin inc(c); Adj[c].v:=v; Adj[c].w:=w; Adj[c].link:=head[u]; head[u]:=c; end; procedure xuly; var i, u, v, w :longint; begin assign(input,fi);assign(output,fo); reset(input);rewrite(output); readln(n, m, k, s, t); c:=0; fillchar(head,sizeof(head),0); for i:=1 to m do begin readln(u,v,w); Tadd(u,v,w); Tadd(v,u,w); end; Dijkstra; close(input);close(output); end; begin xuly; end. |
BÌNH LUẬN MỚI