Hướng dẫn giải của Sa mạc
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận