ROADS - Roads
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
const fi='';
fo='';
maxn=110;
maxm=10010;
maxk=10010;
var n,k,m,re,test,it:longint;
pos,cur,sl,mn:array[1..maxn] of longint;
d:array[1..maxn,0..maxk] of longint;
a,p,t:array[1..maxm] of longint;
b:array[1..maxm,0..3] of longint;
q:array[0..1,1..200000,0..2] of longint;
num:array[0..1] of longint;
procedure rf;
var i,j,x:longint;
begin
fillchar(sl,sizeof(sl),0);
read(k,n,m);
for i:=1 to m do
begin
for j:=0 to 3 do
read(b[i,j]);
inc(sl[b[i,0]]);
end;
pos[1]:=1; cur[1]:=1;
for i:=2 to n+1 do
begin
pos[i]:=pos[i-1]+sl[i-1];
cur[i]:=pos[i];
end;
for i:=1 to m do
begin
x:=cur[b[i,0]];
a[x]:=b[i,1]; t[x]:=b[i,2]; p[x]:=b[i,3];
inc(cur[b[i,0]]);
end;
end;
procedure pr;
var i,z,j,x,pp,y,tt:longint;
begin
fillchar(d,sizeof(d),0);
re:=maxlongint;
z:=1; num[z]:=1; d[1,0]:=1; mn[1]:=0;
q[z,1,0]:=1; q[z,1,1]:=0; q[z,1,2]:=1;
repeat
z:=1-z; num[z]:=0; i:=1;
repeat
x:=q[1-z,i,0]; pp:=q[1-z,i,1]; tt:=q[1-z,i,2];
if (tt>d[x,pp]) then
begin
i:=i+1;
continue;
end;
for j:=pos[x] to pos[x+1]-1 do
if (pp+p[j]<=k) and (tt+t[j]<re) then
begin
y:=d[a[j],pp+p[j]];
if (y=0) or (y>tt+t[j]) then
begin
if (a[j]<n) and (a[j]>1) then
begin
num[z]:=num[z]+1;
q[z,num[z],0]:=a[j];
q[z,num[z],1]:=pp+p[j];
q[z,num[z],2]:=tt+t[j];
end;
if a[j]=n then
re:=min(re,tt+t[j]);
d[a[j],pp+p[j]]:=tt+t[j];
end;
end;
i:=i+1;
until i>num[1-z];
if num[z]=0 then break;
until false;
if re=maxlongint then writeln(-1)
else writeln(re-1);
end;
begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
read(test);
for it:=1 to test do
begin
rf;
pr;
end;
close(input); close(output);
end.