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.

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

Please read the guidelines before commenting.


There are no comments at the moment.