Hướng dẫn giải của Vị trí tốt nhất
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
const maxn=510; maxm=8010; oo=10000000; var n,m,q,re,r,nh:longint; a,c:array[0..maxm shl 1] of longint; sl,pos,cur,h,p,e:array[0..maxn] of longint; d:array[1..maxn,1..maxn] of longint; b:array[0..maxm,0..2] of longint; free:array[0..maxn] of boolean; procedure rf; var i:longint; begin read(n,q,m); for i:=1 to q do read(e[i]); for i:=1 to m do begin read(b[i,0],b[i,1],b[i,2]); inc(sl[b[i,0]]); inc(sl[b[i,1]]); 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 a[cur[b[i,0]]]:=b[i,1]; c[cur[b[i,0]]]:=b[i,2]; inc(cur[b[i,0]]); a[cur[b[i,1]]]:=b[i,0]; c[cur[b[i,1]]]:=b[i,2]; inc(cur[b[i,1]]); end; end; procedure update(z,x:longint); var cha,con:longint; begin con:=p[x]; if con=0 then begin inc(nh); con:=nh; end; cha:=con shr 1; while (cha>0) and (d[z,h[cha]]>d[z,x]) do begin h[con]:=h[cha]; p[h[con]]:=con; con:=cha; cha:=con shr 1; end; h[con]:=x; p[x]:=con; end; function pop(z:longint):longint; var x,cha,con:longint; begin pop:=h[1]; x:=h[nh]; dec(nh); cha:=1; con:=2; while con<=nh do begin if (con<nh) and (d[z,h[con+1]]<d[z,h[con]]) then inc(con); if d[z,x]<=d[z,h[con]] then break; h[cha]:=h[con]; p[h[cha]]:=cha; cha:=con; con:=cha shl 1; end; h[cha]:=x; p[x]:=cha; end; procedure dijk(x:longint); var i,j,y,u:longint; begin for i:=1 to n do begin free[i]:=true; d[x,i]:=oo; p[i]:=0; h[i]:=0; end; d[x,x]:=0; nh:=0; update(x,x); repeat y:=pop(x); free[y]:=false; for j:=pos[y] to pos[y+1]-1 do begin u:=a[j]; if free[u] and (d[x,u]>d[x,y]+c[j]) then begin d[x,u]:=d[x,y]+c[j]; update(x,u); end; end; until nh=0; end; procedure pr; var i,s,j:longint; begin for i:=1 to q do dijk(e[i]); re:=maxlongint; for i:=1 to n do begin s:=0; for j:=1 to q do s:=s+d[e[j],i]; if s<re then begin re:=s; r:=i; end; end; writeln(r); end; begin rf; pr; end.
Code mẫu của happyboy99x
#include<cstdio> #include<climits> #include<algorithm> #include<queue> #include<vector> using namespace std; #define INF 1000000000 #define N 500 #define REP(i, n) for(int i = 0; i < (n); ++i) typedef pair<int, int> ii; int favor[N], a[N][N], n, f, c; vector<vector<ii> > g; void enter() { scanf("%d%d%d",&n,&f,&c); for(int i = 0; i < f; favor[i++]--) scanf("%d", favor+i); g.resize(n); for(int u, v, l, i = 0; i < c; ++i) { scanf("%d%d%d",&u,&v,&l); g[--u].push_back(ii(--v,l)); g[v].push_back(ii(u,l)); } } void dijkstra(int s, int d[]) { REP(u, n) d[u] = INF; d[s] = 0; priority_queue<ii, vector<ii>, greater<ii> > q; q.push(ii(0, s)); while(!q.empty()) { int u = q.top().second, du = q.top().first; q.pop(); if(du > d[u]) continue; for(vector<ii>::iterator it = g[u].begin(); it != g[u].end(); ++it) { int v = it->first, l = it->second; if(du + l < d[v]) q.push(ii(d[v] = du + l, v)); } } } void solve() { REP(u, n) dijkstra(u, a[u]); int mn = INT_MAX, pos = 0; REP(i,n) { int total = 0; for(int j=0; j < f; total += a[i][favor[j++]]); if(total < mn) mn = total, pos = i; } printf("%d\n", pos+1); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
program bestspot; uses math; type e=record v,w,link:longint; end; const maxn=555; maxm=16003; fi=''; oo=trunc(1e7); var head,des,d,q:array[0..maxn] of longint; inq:array[1..maxn] of boolean; adj:array[1..maxm] of e; n,f,c,m,res,choose,nq:longint; procedure input; var inp:text; i,x,w,y:longint; begin assign(inp,fi);reset(inp); readln(inp,n,f,c); for i:=1 to f do readln(inp,des[i]); for i:=1 to c 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; close(inp); end; procedure BellmanFord(g:longint); var u,i,l,r:longint; v:e; begin for i:=1 to n do begin d[i]:=oo; inq[i]:=false; end; l:=0;r:=0; q[0]:=g; nq:=1; d[g]:=0; repeat u:=q[l]; l:=(l+1) mod maxn;dec(nq); inq[u]:=false; i:=head[u]; while i>0 do begin v:=adj[i]; if d[v.v]>d[u]+v.w then begin d[v.v]:=d[u]+v.w; if not inq[v.v] then begin inq[v.v]:=true; r:=(r+1) mod maxn; inc(nq); q[r]:=v.v; end; end; i:=v.link; end; until nq=0; end; procedure process; var i,j,sum:longint; begin res:=high(longint); for i:=1 to n do begin BellmanFord(i); sum:=0; for j:=1 to f do inc(sum,d[des[j]]); if sum<res then begin res:=sum; choose:=i; end; end; end; begin input; process; write(choose); end.
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R+,Q+} {$Mode objFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 555; oo = 1000111000; type list = ^node; node = record u,c:longint; next:list; end; Theap = object val : array[1..MAXN] of longint; pos : array[1..MAXN] of longint; size : longint; function lower(a,b:longint):boolean; procedure down(i:longint); procedure up(i:longint); procedure push(u:longint); procedure pop(var u:longint); end; var f1,f2 : text; n,sp : longint; p : array[1..MAXN] of longint; ke : array[1..MAXN] of list; heap : Theap; d,sum : array[1..MAXN] of longint; 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); inline; 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,sp,m); for u:=1 to sp do read(f1,p[u]); for m:=1 to m do begin read(f1,u,v,c); add(v,c,ke[u]); add(u,c,ke[v]); end; end; function Theap.lower(a,b:longint):boolean; inline; begin exit(d[val[a]]<d[val[b]]); end; procedure swap(var a,b:longint); inline; var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure Theap.down(i:longint); var j:longint; begin j:=i<<1; while (j<=size) do begin if (j<size) and lower(j+1,j) then inc(j); if lower(j,i) then begin swap(pos[val[i]],pos[val[j]]); swap(val[i],val[j]); end else exit; i:=j; j:=i<<1; end; end; procedure Theap.up(i:longint); var j:longint; begin j:=i>>1; while (i>1) and lower(i,j) do begin swap(pos[val[i]],pos[val[j]]); swap(val[i],val[j]); i:=j; j:=i>>1; end; end; procedure Theap.push(u:longint); begin inc(size); val[size]:=u; pos[u]:=size; up(size); end; procedure Theap.pop(var u:longint); begin u:=val[1]; pos[u]:=0; swap(val[1],val[size]); pos[val[1]]:=1; dec(size); down(1); end; procedure ijk(start:longint); var u,v,c:longint; p:list; begin for u:=1 to n do d[u]:=oo; with heap do begin size:=0; fillchar(pos,sizeof(pos),0); end; d[start]:=0; heap.push(start); while heap.size>0 do begin heap.pop(u); p:=ke[u]; while p<>nil do begin v:=p^.u; c:=p^.c; p:=p^.next; if d[v]>d[u]+c then begin d[v]:=d[u]+c; if heap.pos[v]=0 then heap.push(v) else heap.up(heap.pos[v]); end; end; end; end; procedure update; var u:longint; begin for u:=1 to n do inc(sum[u],d[u]); end; procedure solve; var i:longint; begin for i:=1 to sp do begin ijk(p[i]); update; end; end; procedure ans; var best,i:longint; begin best:=1; for i:=2 to n do if sum[i]<sum[best] then best:=i; writeln(f2,best); end; begin openF; inp; solve; ans; closeF; end.
Code mẫu của ll931110
{$MODE DELPHI} Program BESTSPOT; Const input = ''; output = ''; maxn = 501; maxm = 16000; maxc = 10000000; Var a,d,heap,pos,h: array[1..maxn] of integer; adj,cost,x,y,adjcost: array[1..maxm] of integer; free: array[1..maxn] of boolean; n,f,m: integer; nHeap: integer; Procedure init; Var fi: text; i,j,u,v: integer; Begin Assign(fi, input); Reset(fi); Readln(fi,n,f,m); For i:= 1 to f do readln(fi, a[i]); Fillchar(h, sizeof(h), 0); For i:= 1 to m do Begin Readln(fi, x[i], y[i], cost[i]); inc(h[x[i]]); inc(h[y[i]]); End; Close(fi); For i:= 2 to n do h[i]:= h[i] + h[i - 1]; For i:= 1 to m do Begin adj[h[x[i]]]:= y[i]; adjcost[h[x[i]]]:= cost[i]; dec(h[x[i]]); adj[h[y[i]]]:= x[i]; adjcost[h[y[i]]]:= cost[i]; dec(h[y[i]]); End; h[n + 1]:= 2 * m; End; Procedure update(v: integer); Var parent,child: integer; Begin child:= pos[v]; If child = 0 then Begin inc(nHeap); child:= nHeap; End; parent:= child div 2; While (parent > 0) and (d[heap[parent]] > d[v]) do Begin heap[child]:= heap[parent]; pos[heap[child]]:= child; child:= parent; parent:= child div 2; End; heap[child]:= v; pos[v]:= child; End; Function pop: integer; Var r,c,v: integer; Begin pop:= heap[1]; v:= heap[nHeap]; dec(nHeap); r:= 1; While r * 2 <= nHeap do Begin c:= r * 2; If (c < nHeap) and (d[heap[c + 1]] < d[heap[c]]) then inc(c); If d[v] <= d[heap[c]] then break; heap[r]:= heap[c]; pos[heap[r]]:= r; r:= c; End; heap[r]:= v; pos[v]:= r; End; Procedure Dijkstra(s: integer); Var u,v,i,iv: integer; Begin Fillchar(pos, sizeof(pos), 0); nHeap:= 0; For i:= 1 to n do d[i]:= maxc; d[s]:= 0; Fillchar(free, sizeof(free), true); update(s); Repeat u:= pop; free[u]:= false; For iv:= h[u] + 1 to h[u + 1] do Begin v:= adj[iv]; If free[v] and (d[v] > d[u] + adjcost[iv]) then Begin d[v]:= d[u] + adjcost[iv]; update(v); End; End; Until nHeap = 0; End; Procedure solve; Var fo: text; min,u,i,j,tmp: integer; Begin min:= maxc; For i:= 1 to n do Begin Dijkstra(i); tmp:= 0; For j:= 1 to f do tmp:= tmp + d[a[j]]; If tmp < min then Begin min:= tmp; u:= i; End; End; Assign(fo, output); Rewrite(fo); Writeln(fo, u); Close(fo); End; Begin init; solve; End.
Bình luận