ROADS - Roads

Tác giả: ladpro98

Ngôn ngữ: Pascal

{$MODE OBJFPC}
program roads;
uses    math;
const   maxn=111;
        maxm=maxn*maxn;
        maxk=10011;
        oo=trunc(1e9);
        fi='';
type    e=record
        v,w,t,link:longint;
        end;
        ver=record
        v,t:longint;
        end;
var     a:array[1..maxm] of e;
        head:array[1..maxn] of longint;
        d,pos:array[1..maxn,0..maxK] of longint;
        h:array[1..maxn*maxK] of ver;
        inp:text;
        m,n,k,t,tt,nh,res:longint;

procedure input;
var     i,x:longint;
begin
        readln(inp,k);
        readln(inp,n);
        readln(inp,m);
        for i:=1 to n do head[i]:=0;
        for i:=1 to m do begin
                readln(inp,x,a[i].v,a[i].w,a[i].t);
                a[i].link:=head[x];
                head[x]:=i;
        end;
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].v,h[p].t]<=d[u,v]) then break;
                h[c]:=h[p];
                pos[h[c].v,h[c].t]:=c;
                c:=p;
        until false;
        h[c].v:=u;h[c].t:=v;
        pos[u,v]:=c;
end;

function extract:ver;
var     p,c:longint;
        v:ver;
begin
        result:=h[1];
        v:=h[nh];
        dec(nh);
        p:=1;
        repeat
                c:=p shl 1;
                if (c<nh) and (d[h[c+1].v,h[c+1].t]<d[h[c].v,h[c].t]) then inc(c);
                if (c>nh) or (d[h[c].v,h[c].t]>=d[v.v,v.t]) then break;
                h[p]:=h[c];
                pos[h[p].v,h[p].t]:=p;
                p:=c;
        until false;
        h[p]:=v;
        pos[v.v,v.t]:=p;
end;

procedure dijkstra;
var     i,j:longint;
        u:ver;
        v:e;
begin
        for i:=2 to n do
        for j:=0 to k do begin
                d[i,j]:=oo;
                pos[i,j]:=0;
        end;
        nh:=0;res:=-1;
        update(1,k);
        repeat
                u:=extract;
                if (u.v=n) then begin
                        res:=d[u.v,u.t];
                        exit;
                end;
                i:=head[u.v];
                while i>0 do begin
                        v:=a[i];
                        if (v.t<=u.t) and (d[v.v,u.t-v.t]>d[u.v,u.t]+v.w) then begin
                                d[v.v,u.t-v.t]:=d[u.v,u.t]+v.w;
                                update(v.v,u.t-v.t);
                        end;
                        i:=v.link;
                end;
        until nh=0;
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,t);
        for tt:=1 to t do begin
                input;
                dijkstra;
                writeln(res);
        end;
end.

Download