ROADS - Roads
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
const
FINP='';
FOUT='';
MAXN=101;
MAXK=10001;
MAXM=20001;
oo=1000000000;
type
rec=record v,c,k:longint; end;
var
test,t,hsize,fk,n,m,sumk:longint;
eu,ev,ec,ek:array[1..MAXM] of longint;
e:array[1..MAXM] of rec;
dx,deg,startof:array[0..MAXN] of longint;
d,hpos:array[1..MAXN,0..MAXK] of longint;
hu,hv:array[1..MAXN*MAXK] of longint;
f1,f2:text;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i,u,v:longint;
begin
read(f1,sumk,n,m);
for i:=1 to m do
begin
read(f1,u,v,ec[i],ek[i]);
eu[i]:=u; ev[i]:=v;
inc(deg[u]);
end;
end;
procedure init;
var
i,j,u,v:longint;
begin
for i:=1 to n do
for j:=0 to sumk do
d[i,j]:=oo;
startof[1]:=1;
for i:=2 to n+1 do
startof[i]:=startof[i-1]+deg[i-1];
for i:=1 to m do
begin
u:=eu[i]; v:=ev[i];
j:=startof[u]+dx[u];
e[j].v:=v; e[j].c:=ec[i]; e[j].k:=ek[i];
inc(dx[u]);
end;
end;
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
function smaller(u1,v1,u2,v2:longint):boolean;
begin
smaller:=(d[u1,v1]<d[u2,v2]) or ((d[u1,v1]=d[u2,v2]) and (v1<v2));
end;
procedure downHeap(i:longint);
var
j:longint;
begin
j:=i shl 1;
while (j<=hsize) do
begin
if (j<hsize) and smaller(hu[j+1],hv[j+1],hu[j],hv[j]) then inc(j);
if smaller(hu[j],hv[j],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 smaller(hu[i],hv[i],hu[j],hv[j]) 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,k,i,v,kk:longint;
begin
fk:=0;
d[1,0]:=0; hsize:=0;
push(1,0);
while hsize>0 do
begin
pop(u,k);
if u=n then
begin
fk:=k;
exit;
end;
for i:=startof[u] to startof[u+1]-1 do
begin
v:=e[i].v; kk:=k+e[i].k;
if (kk<=sumk) and (d[u,k]+e[i].c<d[v,kk]) then
begin
d[v,kk]:=d[u,k]+e[i].c;
if hpos[v,kk]=0 then push(v,kk)
else upHeap(hpos[v,kk]);
end;
end;
end;
end;
begin
openF;
read(f1,t);
for test:=1 to t do
begin
fillchar(dx,sizeof(dx),0);
fillchar(hpos,sizeof(hpos),0);
fillchar(deg,sizeof(deg),0);
inp;
init;
solve;
if (fk=0) then writeln(f2,-1)
else writeln(f2,d[n,fk]);
end;
closeF;
end.