首页 > 代码库 > 【CF707B】Bakery（想法题）
【CF707B】Bakery（想法题）
题意：
有N个城市，M条无向边，其中有K个城市是仓库
现在要在非仓库的城市中选择一家开面包店，使得其最少与一个仓库联通，且到所有仓库距离的最小值最小
(1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ n)
分析：
数据范围决定了只能使用O(N)或O(n log n)的解法
思考后可以发现面包店一定选在与某仓库直接相连的城市中
否则就要通过另外间接相连的城市走到，多走了若干条路
1 var a,b,c,flag:array[1..100000]of longint; 2 n,m,k,i,ans,x:longint; 3 4 begin 5 readln(n,m,k); 6 for i:=1 to m do readln(a[i],b[i],c[i]); 7 for i:=1 to k do 8 begin 9 read(x);10 flag[x]:=1;11 end;12 ans:=maxlongint;13 for i:=1 to m do14 if flag[a[i]]+flag[b[i]]=1 then15 if c[i]<ans then ans:=c[i];16 if ans<maxlongint then writeln(ans)17 else writeln(-1);18 end.
【CF707B】Bakery（想法题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。