【CF707B】Bakery（想法题）

题意：

有N个城市，M条无向边，其中有K个城市是仓库

现在要在非仓库的城市中选择一家开面包店，使得其最少与一个仓库联通，且到所有仓库距离的最小值最小

(1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ n)

分析：

数据范围决定了只能使用O(N)或O(n log n)的解法

思考后可以发现面包店一定选在与某仓库直接相连的城市中

否则就要通过另外间接相连的城市走到，多走了若干条路

var a,b,c,flag:array[1..100000]of longint;
    n,m,k,i,ans,x:longint;

begin
 readln(n,m,k);
 for i:=1 to m do readln(a[i],b[i],c[i]);
 for i:=1 to k do
 begin
  read(x);
  flag[x]:=1;
 end;
 ans:=maxlongint;
 for i:=1 to m do
  if flag[a[i]]+flag[b[i]]=1 then
   if c[i]<ans then ans:=c[i];
 if ans<maxlongint then writeln(ans)
  else writeln(-1);
end.