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.

Download