BESTSPOT - Vị trí tốt nhất

Tác giả: ll931110

Ngôn ngữ: Pascal

{$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.

Download