Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

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);
for i:=1 to m do
begin
for j:=0 to 3 do
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);
for it:=1 to test do
begin
rf;
pr;
end;
close(input); close(output);
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
struct edge {
int v, l, c; //vertex, length, cost
edge(int v, int l, int c): v(v), l(l), c(c) {}
bool operator < (const edge &a) const {
return l > a.l;
}
};
const int N = 111, K = 11111, INF = 1e9;
int d[N][K], n, k, m;
vector<vector<edge> > g;

void enter() {
scanf("%d%d%d", &k, &n, &m);
g.assign(n, vector<edge>());
for(int i = 0; i < m; ++i) {
int u, v, l, c;
scanf("%d%d%d%d", &u, &v, &l, &c);
g[--u].push_back(edge(--v, l, c));
}
}

void dijkstra() {
memset(d, 0x3f, sizeof d); d[0][k] = 0;
priority_queue<edge> q; q.push(edge(0, 0, k));
while(!q.empty()) {
int u = q.top().v, dumo = q.top().l, mo = q.top().c; q.pop();
if(dumo > d[u][mo]) continue;
if(u == n-1) {
printf("%d\n", dumo);
return;
}
TR(g[u], it) {
int v = it->v, w = it->l, c = it->c;
if(mo >= c && d[v][mo - c] > dumo + w)
q.push(edge(v, d[v][mo - c] = dumo + w, mo - c));
}
}
printf("-1\n");
}

int main() {
int tc; scanf("%d", &tc);
while(tc--) {
enter();
dijkstra();
}
return 0;
}


{$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.  #### Code mẫu của RR {$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
for i:=1 to m do
begin
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;
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.


#### Code mẫu của ll931110

{\$MODE DELPHI}
Const
input  = '';
output = '';
maxn = 101;
maxk = 10000;
Type
rec = record
kx,ky: integer;
end;
Var
h: array[1..maxn + 1] of integer;
x,y,c,l: array[1..maxk] of integer;
pos,d: array[1..maxn,0..maxk] of integer;
heap: array[1..maxn * maxk] of rec;
fi,fo: text;
free: array[1..maxn,0..maxk] of boolean;
k,r,n,t,i,nHeap: integer;

Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);

Assign(fo, output);
Rewrite(fo);
End;

Procedure init;
Var
i: integer;
Begin
Fillchar(h, sizeof(h), 0);

For i:= 1 to r do
Begin
inc(h[x[i]]);
End;

For i:= 2 to n do h[i]:= h[i] + h[i - 1];
For i:= 1 to r do
Begin
dec(h[x[i]]);
End;

h[n + 1]:= r;
End;

Function low(u,v: rec): boolean;
Begin
low:= d[u.kx,u.ky] < d[v.kx,v.ky];
End;

Procedure update(v: rec);
Var
parent,child: integer;
Begin
child:= pos[v.kx,v.ky];
If child  = 0 then
Begin
inc(nHeap);
child:= nHeap;
End;

parent:= child div 2;
While (parent > 0) and low(v,heap[parent]) do
Begin
heap[child]:= heap[parent];
pos[heap[child].kx,heap[child].ky]:= child;

child:= parent;
parent:= child div 2;
End;

heap[child]:= v;
pos[v.kx,v.ky]:= child;
End;

Function pop: rec;
Var
re,rc: integer;
v: rec;
Begin
pop:= heap[1];
v:= heap[nHeap];
dec(nHeap);

re:= 1;
While (re * 2 <= nHeap) do
Begin
rc:= re * 2;
If (rc < nHeap) and low(heap[rc + 1],heap[rc]) then inc(rc);
If not low(heap[rc],v) then break;

heap[re]:= heap[rc];
pos[heap[re].kx,heap[re].ky]:= re;
re:= rc;
End;

heap[re]:= v;
pos[v.kx,v.ky]:= re;
End;

Procedure Dijkstra;
Var
iv,v,i,j: integer;
u,s: rec;
Begin
Fillchar(pos, sizeof(pos), 0);
Fillchar(free, sizeof(free), true);
nHeap:= 0;

For i:= 1 to n do
For j:= 0 to k do d[i,j]:= maxn * maxk;
d[1,k]:= 0;

u.kx:= 1;
u.ky:= k;
update(u);

Repeat
u:= pop;
free[u.kx,u.ky]:= false;

For iv:= h[u.kx] + 1 to h[u.kx + 1] do
Begin

If (s.ky >= 0) and free[s.kx,s.ky]
and (d[s.kx,s.ky] > d[u.kx,u.ky] + adjlen[iv]) then
Begin
update(s);
End;
End;
Until nHeap = 0;
End;

Procedure printresult;
Var
i: integer;
min: integer;
Begin
min:= maxn * maxk;
For i:= k downto 0 do
if min > d[n,i] then min:= d[n,i];

If min = maxn * maxk then writeln(fo, -1) else writeln(fo, min);
End;

Procedure closefile;
Begin
Close(fo);
Close(fi);
End;

Begin
openfile;

For i:= 1 to t do
Begin
init;
Dijkstra;
printresult;
End;

closefile;
End.