Editorial for Sa mạc
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 happyboy99x
#include<cstdio> #include<vector> #include<queue> using namespace std; #define fi first #define se second #define TR(v, it) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it) #define INF 1000000000 typedef long long LL; typedef pair<LL, LL> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<LL> vi; vvii g; LL n, m, c; void enter() { scanf("%lld%lld%lld",&n,&m,&c); g = vvii(n, vii()); for(LL i = 0; i < m; ++i) { LL u, v, l; scanf("%lld%lld%lld",&u,&v,&l); g[--u].push_back(ii(--v, l)); g[v].push_back(ii(u, l)); } } inline LL ceil(int a, int b) { return b <= 0 ? INF : a / b + (a % b != 0); } void solve() { //Dijkstra's Algorithm vi d = vi(n, INF); d[n-1] = 0; priority_queue<ii, vii, greater<ii> > qu; qu.push(ii(0, n-1)); while(!qu.empty()) { LL du = qu.top().fi, u = qu.top().se; qu.pop(); if (du > d[u]) continue; TR(g[u], it) { LL v = it->fi, l = it->se; if(du + l <= c) { if(du + l < d[v]) qu.push(ii(d[v] = du + l, v)); } else { LL k = ceil(du - c + l, c - l - l); if(k != INF && (k+k+1)*l + du < d[v]) qu.push(ii(d[v] = (k+k+1)*l + du, v)); } } } printf("%lld\n", d.front()); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif LL tc; scanf("%lld", &tc); while(tc--) { enter(); solve(); } return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung (algorithm by taek) {$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=101; oo=1000000000000; type list=^node; node=record u,c:longint; next:list; end; var f1,f2:text; test,n,gh,hsize:longint; ke:array[1..MAXN] of list; h,hpos:array[1..MAXN] of longint; need:array[1..MAXN] of int64; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure add(u,c:longint; var a:list); var p:list; begin new(p); p^.u:=u; p^.c:=c; p^.next:=a; a:=p; end; procedure inp; var m,u,v,c:longint; begin read(f1,n,m,gh); fillchar(ke,sizeof(ke),0); for m:=1 to m do begin read(f1,u,v,c); add(u,c,ke[v]); add(v,c,ke[u]); end; end; procedure ans; begin if need[1]=oo then writeln(f2,-1) else writeln(f2,need[1]); end; //Xu ly heap procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure downHeap(i:longint); var j:longint; begin j:=i<<1; while (j<=hsize) do begin if (j<hsize) and (need[h[j+1]]<need[h[j]]) then inc(j); if (need[h[j]]<need[h[i]]) then begin swap(hpos[h[i]],hpos[h[j]]); swap(h[i],h[j]); end; i:=j; j:=i<<1; end; end; procedure upHeap(i:longint); var j:longint; begin j:=i>>1; while (i>1) and (need[h[i]]<need[h[j]]) do begin swap(hpos[h[i]],hpos[h[j]]); swap(h[i],h[j]); i:=j; j:=i>>1; end; end; procedure push(u:longint); begin inc(hsize); h[hsize]:=u; hpos[u]:=hsize; upHeap(hsize); end; procedure pop(var u:longint); begin u:=h[1]; hpos[u]:=0; swap(h[1],h[hsize]); hpos[h[1]]:=1; dec(hsize); downHeap(1); end; procedure solve; var u,v:longint; x,one,c:int64; p:list; begin for u:=1 to n-1 do need[u]:=oo; need[n]:=0; hsize:=0; fillchar(hpos,sizeof(hpos),0); push(n); while hsize>0 do begin pop(u); p:=ke[u]; while p<>nil do begin v:=p^.u; c:=p^.c; p:=p^.next; //Khong the qua canh (u,v) if c>gh then continue; //Chi can luong <=gh-c de den dich (chi can qua canh (u,v) 1 lan) if need[u]<=gh-c then x:=need[u]+c else if gh-c<<1<=0 then continue else begin //Luong nuoc chuyen duoc trong 1 lan one:=(need[u]-(gh-c)-1) div (gh-c<<1)+1; //Luong nuoc can x:=need[u]+(one<<1+1)*c; end; if x<need[v] then begin need[v]:=x; if hpos[v]=0 then push(v) else upHeap(hpos[v]); end; end; end; end; begin openF; read(f1,test); for test:=1 to test do begin inp; solve; ans; end; closeF; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> long long min(long long a,long long b) { if(a<b) return a; else return b; } int main() { long long A = 1000000000, B = 1000000; long long oo = A*B; //freopen("NK05DSRT.in","r",stdin); int test,flag[101],n,m,c,x,y,l; long long a[101][101],d[101]; scanf("%d",&test); for(int ii = 1;ii<=test;ii++) { scanf("%d %d %d",&n,&m,&c); for(int i = 1;i<=n;i++) { d[i] = oo; flag[i] = 0; for(int j = 1;j<=n;j++) a[i][j] = oo; } for(int i = 1;i<=m;i++) { scanf("%d %d %d",&x,&y,&l); if(a[x][y]>l) { a[x][y] = l; a[y][x] = l; } } int u = n;flag[n] = 1;d[n]=0; while(u!=1) { for(int i = 1;i<=n;i++) if(flag[i]==0 && a[i][u] < oo) { long long k = oo; if(a[i][u]>c); else if(d[u]+a[i][u]<=c) k = d[u]+a[i][u]; else if(c>2*a[i][u]) { long long t = (d[u]-c+a[i][u]-1)/(c-2*a[i][u])+1; k = t*c+d[u]-t*(c-2*a[i][u])+a[i][u]; } d[i] = min(k,d[i]); } long long f = 0,minn = oo; for(int i = 1;i<=n;i++) if(flag[i]==0 && d[i]<minn) { f = i; minn = d[i]; } u = f; flag[f] = 1; //for(int i = 1;i<=n;i++) //printf("%d ",d[i]); //printf(" ___%d____",u); //printf("\n"); } printf("%lld\n",d[1]); } //getch(); }
Code mẫu của khuc_tuan
#include <iostream> #include <vector> #include <algorithm> #include <stdio.h> #include <queue> using namespace std; int N, C; int a[111][111]; long long d[111]; void process() { memset( d, 0x3f, sizeof(d)); d[N] = 0; queue<int> q; q.push(N); while(!q.empty()) { int u = q.front(), v; long long L, tmp, k, xx; q.pop(); for(v=1;v<=N;++v) if((L=a[u][v])>0 && a[u][v]<=C){ // 1 lan if(C-L>=d[u]) { tmp = d[u] + L; if(d[v]>tmp) { d[v] = tmp; q.push(v); } } // nhieu lan else if(C>2*L) { xx = (d[u]+L-C) / (C-2*L) - 1; xx >?= 1; for(k=xx;k<=xx+10;++k) { tmp = d[u] + L - k * (C - 2*L); if(tmp>=L && tmp<=C) { tmp = tmp + k * C; if(d[v]>tmp) { d[v] = tmp; q.push(v); } } } } } } printf("%lld\n",d[1]); } int main() { int st, M, u, v, l; scanf("%d",&st); while(st--) { scanf("%d%d%d",&N,&M,&C); memset( a, 0, sizeof(a)); for(int i=0;i<M;++i) { scanf("%d%d%d",&u,&v,&l); a[u][v] = a[v][u] = l; } process(); } return 0; }
Comments