DHFRBUS – SPOJ

18/04/2016 by Leave a Comment

Đề 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.
Chủ đề: Dijkstra, SPOJ, Thuật toán Mức độ: , , , ,