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.