Editorial for Roads
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.
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); 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.
Comments