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);
     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.

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;
}

Code mẫu của ladpro98

{$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
  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.

Code mẫu của ll931110

{$MODE DELPHI}
Program ROADS;
Const
  input  = '';
  output = '';
  maxn = 101;
  maxk = 10000;
Type
  rec = record
    kx,ky: integer;
  end;
Var
  h: array[1..maxn + 1] of integer;
  adj,adjlen,adjcost: array[1..maxk] 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
  Read(fi, k, n, r);
  Fillchar(h, sizeof(h), 0);

  For i:= 1 to r do
    Begin
      Readln(fi, x[i], y[i], l[i], c[i]);
      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
      adj[h[x[i]]]:= y[i];
      adjlen[h[x[i]]]:= l[i];
      adjcost[h[x[i]]]:= c[i];
      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
        s.kx:= adj[iv];
        s.ky:= u.ky - adjcost[iv];

        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
              d[s.kx,s.ky]:= d[u.kx,u.ky] + adjlen[iv];
              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;

  Readln(fi, t);
  For i:= 1 to t do
    Begin
      init;
      Dijkstra;
      printresult;
    End;

  closefile;
End.