Editorial for Dạo chơi đồng 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 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()
Comments