Hướng dẫn giải của Dạo chơi đồng 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 flashmt
#include<iostream> #include<algorithm> #define fr(a,b,c) for(a=b;a<=c;a++) #define frr(a,b,c) for(a=b;a>=c;a--) #define maxn 1010 using namespace std; int n,a[maxn][maxn],e[maxn][11],d[maxn],f[maxn],h[maxn]; void visit(int x,int y) { d[x]=y; int i; fr(i,1,n) if (i!=y && a[x][i]) { f[i]=f[x]+a[x][i]; h[i]=h[x]+1; visit(i,x); } } int lca(int x,int y) { int i; if (h[x]<h[y]) swap(x,y); frr(i,10,0) if (h[x]-(1<<i)>=h[y]) x=e[x][i]; if (x==y) return x; frr(i,10,0) if (e[x][i]!=-1 && e[x][i]!=e[y][i]) x=e[x][i], y=e[y][i]; return d[x]; } int main() { int q,i,j,x,y,z; cin >> n >> q; fr(i,1,n-1) { cin >> x >> y >> z; a[x][y]=z; a[y][x]=z; } fr(i,1,n) fr(j,0,10) e[i][j]=-1; visit(1,0); d[1]=-1; fr(i,2,n) e[i][0]=d[i]; fr(j,1,10) fr(i,1,n) if (e[i][j-1]!=-1) e[i][j]=e[e[i][j-1]][j-1]; while (q--) { cin >> x >> y; z=lca(x,y); cout << f[x]+f[y]-2*f[z] << endl; } return 0; }
Code mẫu của happyboy99x
#include<cstdio> #include<vector> #include<queue> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; #define tr(v,it) for(typeof((v).begin())it=(v).begin(),_e=(v).end();it!=_e;++it) const int N = 1005; vvii g; int d[N][N], n, q; bool vst[N]; void bfs(int u) { queue<int> qu; d[u][u] = 0; fill(vst, vst+n, 0); vst[u] = 1; qu.push(u); while( !qu.empty() ) { int v = qu.front(); qu.pop(); tr(g[v], it) { int w = it->first, l = it->second; if(vst[w] == 0) { d[u][w] = d[u][v] + l; vst[w] = 1; qu.push(w); } } } } int main() { //freopen( "inp", "r", stdin ); scanf( "%d%d", &n, &q ); g = vvii(n, vii()); for(int u, v, l, i = 1; i < n; ++i ) { scanf( "%d%d%d", &u, &v, &l ); g[--u].push_back(ii(--v, l)); g[v].push_back(ii(u,l)); } for(int i = 0; i < n; ++i) bfs(i); for(int u, v, i = 0; i < q; ++i) { scanf( "%d%d", &u, &v ); printf( "%d\n", d[--u][--v]); } return 0; }
Code mẫu của ladpro98
program lubenica; uses math; type e=record v,w,link:longint; end; const maxn=10000; fi=''; var adj:array[0..maxn] of e; head,q,d,cha,w:array[0..maxn] of longint; b,sum:array[0..maxn,0..200] of longint; check:array[0..maxn] of boolean; inp:text; n,m,log,k,tt,res,u,v:longint; procedure input; var //inp:text; i,x,y,w:longint; begin assign(inp,fi); reset(inp); readln(inp,n,k); for i:=1 to n-1 do begin readln(inp,x,y,w); inc(m); adj[m].v:=y; adj[m].w:=w; adj[m].link:=head[x]; head[x]:=m; inc(m); adj[m].v:=x; adj[m].w:=w; adj[m].link:=head[y]; head[y]:=m; end; end; procedure init; var l,r,i,u,j:longint; v:e; begin l:=1;r:=1; q[1]:=1; d[1]:=0; check[1]:=true; while l<=r do begin u:=q[l];inc(l); i:=head[u]; while i>0 do begin v:=adj[i]; if (not check[v.v]) then begin check[v.v]:=true; inc(r); q[r]:=v.v; d[v.v]:=d[u]+1; cha[v.v]:=u; w[v.v]:=v.w; end; i:=v.link; end; end; log:=trunc(ln(n)/ln(2))+1; for i:=0 to n do begin b[i,0]:=cha[i]; sum[i,0]:=w[i]; for j:=1 to log do b[i,j]:=-1; end; for j:=1 to log do for i:=0 to n do begin b[i,j]:=b[b[i,j-1],j-1]; sum[i,j]:=sum[i,j-1]+sum[b[i,j-1],j-1]; end; end; function getbit(i,j:longint):longint; begin exit(i shr (j-1) and 1); end; procedure lca(u,v:longint); var t,i:longint; begin res:=0; if d[u]>=d[v] then begin if d[u]>d[v] then begin t:=d[u]-d[v]; for i:=log downto 1 do if getbit(t,i)=1 then begin inc(res,sum[u,i-1]); u:=b[u,i-1]; end; end; if u=v then exit; for i:=log downto 0 do if b[u,i]<>b[v,i] then begin inc(res,sum[u,i]+sum[v,i]); u:=b[u,i]; v:=b[v,i]; end; if b[u,0]=b[v,0] then inc(res,sum[u,0]+sum[v,0]); end else lca(v,u); end; begin input; init; for tt:=1 to k do begin readln(inp,u,v); lca(u,v); writeln(res); end; end.
Code mẫu của RR
{$R+,Q+} const FINP=''; FOUT=''; MAXN=1000; var a,c,d:array[1..MAXN,1..MAXN] of longint; xet,queue,deg:array[1..MAXN] of longint; f1,f2:text; q,n:longint; 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,n,q); for i:=1 to n-1 do begin read(f1,u,v,c[u,v]); c[v,u]:=c[u,v]; inc(deg[u]); a[u,deg[u]]:=v; inc(deg[v]); a[v,deg[v]]:=u; end; end; procedure ans; var i,u,v:longint; begin for i:=1 to q do begin read(f1,u,v); writeln(f2,d[u,v]); end; end; procedure bfs(start:longint); var first,last,u,i,v:longint; begin first:=1; last:=1; queue[1]:=start; fillchar(xet,sizeof(xet),0); xet[start]:=1; while first<=last do begin u:=queue[first]; inc(first); for i:=1 to deg[u] do begin v:=a[u,i]; if xet[v]=0 then begin xet[v]:=1; inc(last); queue[last]:=v; d[start,v]:=d[start,u]+c[u,v]; end; end; end; end; procedure solve; var i:longint; begin for i:=1 to n do bfs(i); end; begin openF; inp; solve; ans; closeF; end.
Code mẫu của hieult
#include <cstdio> //#include <conio.h> struct diemnoi { int num; int a[1001]; int dai[1001]; }; int n,m,x,y,z,f[1001]; diemnoi A[1001]; void tim(int u) { if(u==y ); else { for(int i = 1;i<=A[u].num;i++) { if(f[A[u].a[i]]==0 && A[u].a[i]!=x) { f[A[u].a[i]] = f[u]+A[u].dai[i]; //printf("%d %d\n",A[x].a[i],f[A[x].a[i]]); tim(A[u].a[i]); } } } } int main() { //freopen("PWALK.in","r",stdin); scanf("%d %d",&n,&m); for(int i = 1;i<=n;i++) A[i].num = 0; for(int i = 1;i<n;i++) { scanf("%d %d %d",&x,&y,&z); A[x].num++; A[y].num++; A[x].a[A[x].num] = y; A[y].a[A[y].num] = x; A[x].dai[A[x].num] = z; A[y].dai[A[y].num] = z; } for(int i = 1;i<=m;i++) { scanf("%d %d",&x,&y); for(int j = 1;j<=n;j++) f[j] = 0; tim(x); printf("%d\n",f[y]); } //getch(); }
Code mẫu của ll931110
Program PWALK; Const input = ''; output = ''; Var n,q: integer; head,adj,adjcost,trace,x,y,c: array[1..2000] of integer; fi,fo: text; Procedure LoadGraph; Var i: integer; Begin Assign(fi, input); Reset(fi); Fillchar(head, sizeof(head), 0); Readln(fi, n, q); For i:= 1 to n - 1 do Begin Readln(fi, x[i], y[i], c[i]); inc(head[x[i]]); inc(head[y[i]]); End; For i:= 2 to n do head[i]:= head[i] + head[i - 1]; For i:= 1 to n - 1 do Begin adj[head[x[i]]]:= y[i]; adjcost[head[x[i]]]:= c[i]; dec(head[x[i]]); adj[head[y[i]]]:= x[i]; adjcost[head[y[i]]]:= c[i]; dec(head[y[i]]); End; head[n + 1]:= 2 * (n - 1); End; Procedure DFS(u: integer); Var v: integer; Begin For v:= head[u] + 1 to head[u + 1] do if trace[adj[v]] = 0 then Begin Trace[adj[v]]:= u; DFS(adj[v]); End; End; Procedure solve; Var i,v,s,f: integer; sum: longint; Begin Assign(fo, output); Rewrite(fo); For i:= 1 to q do Begin Fillchar(trace, sizeof(trace), 0); sum:= 0; Readln(fi, s, f); DFS(s); While f <> s do Begin For v:= head[f] + 1 to head[f + 1] do If adj[v] = trace[f] then Begin sum:= sum + adjcost[v]; Break; End; f:= trace[f]; End; Writeln(fo, sum); End; Close(fo); Close(fi); End; Begin LoadGraph; solve; End.
Code mẫu của skyvn97
#include<stdio.h> #include<queue> #include<vector> #define MAX 1111 #define INF 1e9 using namespace std; typedef pair<int,int> ii; typedef vector<ii> vii; int n,q; int d[MAX][MAX]; vii g[MAX]; void loadgraph(void) { scanf("%d",&n); scanf("%d",&q); int i,u,v,w; for (i=1;i<n;i=i+1) { scanf("%d",&u); scanf("%d",&v); scanf("%d",&w); g[u].push_back(ii(v,w)); g[v].push_back(ii(u,w)); } for (u=1;u<=n;u=u+1) for (v=1;v<=n;v=v+1) d[u][v]=INF; } void dijkstra(void) { int i,u,v,w; ii x; for (u=1;u<=n;u=u+1) { priority_queue<ii,vii,greater<ii> > q; q.push(ii(0,u)); while (!q.empty()) { x=q.top(); q.pop(); w=x.first; v=x.second; for (i=0;i<g[v].size();i=i+1) if (d[u][g[v][i].first]>w+g[v][i].second) { d[u][g[v][i].first]=w+g[v][i].second; q.push(ii(w+g[v][i].second,g[v][i].first)); } } } } void process(void) { int i,u,v; for (i=1;i<=q;i=i+1) { scanf("%d",&u); scanf("%d",&v); printf("%d\n",d[u][v]); } } int main(void) { loadgraph(); dijkstra(); process(); }
Code mẫu của khuc_tuan
import gc gc.disable() import sys import psyco psyco.full() [n,q] = [int(x) for x in raw_input().split()] ke = [[] for i in range(n+1)] question = [[] for i in range(q)] lq = [[] for i in range(n+1)] vs = [False for i in range(n+1)] H = [0 for i in range(n+1)] fa= [0 for i in range(n+1)] F = [-1 for i in range(n+1)] L = [i for i in range(n+1)] def getroot(i): if F[i]<0: return i else: return getroot(F[i]) def merge(i,j): i = getroot(i) j = getroot(j) label = L[i] if F[i]<F[j]: F[i] += F[j] F[j] = i L[i] = label else: F[j] += F[i] F[i] = j L[j] = label def dfs(i): vs[i] = True # answer question here for q in lq[i]: u = question[q][0] v = question[q][1] if vs[u] and vs[v]: k = u + v - i LCA = L[getroot(k)] question[q].append(LCA) for kk in ke[i]: if not vs[kk[0]]: H[kk[0]] = H[i] + kk[1] fa[kk[0]] = i dfs(kk[0]) # merge here if fa[i]>0: merge(fa[i], i) def main(): for i in range(n-1): [a,b,c] = [int(x) for x in raw_input().split()] ke[a].append([b,c]) ke[b].append([a,c]) for i in range(q): question[i] = [int(x) for x in raw_input().split()] lq[question[i][0]].append(i) lq[question[i][1]].append(i) dfs(1) for z in question: u = z[0] v = z[1] lca = z[2] result = H[u] + H[v] - 2 * H[lca] print result main()
Bình luận