Editorial for Vị trí tốt nhất
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
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.
Comments