本文主要是介绍Acwing 5475. 聚会【多源bfs】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：https://www.acwing.com/problem/content/5478/
题目描述：
约翰的农场有 n 个谷仓，编号 1∼n，谷仓之间有 m 条双向道路。
所有道路的长度均为 1。
奶牛们可以通过这些道路从任意谷仓到达任意其它谷仓。
任意两个谷仓之间最多只包含一条道路（注意是道路，不是路径）。
不存在道路两端都连接同一个谷仓的情况。
农场中一共有 k 种干草，编号 1∼k。
每个谷仓都存有一种干草，其中第 i 个谷仓存有第 ai 种干草。
每种干草都至少存在于一个谷仓中。
奶牛们计划选择一个谷仓举办干草宴会。
为了让宴会足够丰盛，至少需要将 s 种不同的干草汇集在宴会谷仓。
宴会谷仓本身就包含一种干草，而其它干草就需要从其它谷仓运输。
已知，将一种干草从一个谷仓运至另一个谷仓所需的运输成本等于两谷仓之间的最短路径距离。
请你帮助奶牛们计算，对于每个谷仓，如果挑选其为宴会举办地，则举办宴会需要付出的总运输成本的最小可能值是多少。
输入输出描述：
输入格式
第一行包含四个整数 n,m,k,s。
第二行包含 n 个整数 a1,a2,…,an。
接下来 m 行，每行包含两个整数 u,v，表示第 u 个谷仓和第 v 个谷仓之间存在一条双向道路。
输出格式
共一行，输出 n 个整数，其中第 i 个整数表示在第 i个谷仓举办宴会需要付出的总运输成本的最小可能值。
数据范围
前 3 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10^5，0≤m≤10^5，1≤s≤k≤min(n,100)，1≤ai≤k，1≤u,v≤n，u≠v。
输入样例1：
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
输出样例1：
2 2 2 2 3
输入样例2：
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
输出样例2：
1 1 1 2 2 1 1解题思路：
很久没用多源bfs这个算法了，所以根本就没有往这个算法上想，有一些算法还是需要及时复习复习呀，防止忘记，首先这个题目最暴力的做法就是对每一个点跑一边bfs，但是这个做法时间复杂度是O(n^2)，这个题目n=1e5，这个时间复杂度肯定会tle，但是我们可以发现k=100非常小，也就是干草的种类非常少，我们不妨对每一种干草跑一边bfs,记录每一种干草到所有点的最短距离，也就是说每次bfs有多个起点，这不就是多源bfs吗，最多只有100种干草，所以最多只会跑100遍多源bfs，bfs过程时间为O(n*100)，大概是1e7，然后每一个点都记录了各种干草到这个点的最短距离，对于每一个点我们需要取到k种干草中距离最短的s种，就是每一个点应该输出的答案，所以对于每一个点的k种干草的距离我们需要从小到大排序，时间复杂度为O(n*k*log(k))，大概1e5*100*log(100)，这个时间是勉强可以过的，但是这个题目会卡常，我们在每次多源bfs中不要使用stl中的队列，使用stl中的队列会tle，可以换成数组模拟队列，换成数组模拟就可以过了。
时间复杂度：O(n*klog(k))。
空间复杂度：O(n*100)，n表示点的个数。
cpp代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;
typedef long long LL;const int N=1e5+10,M=N*2;int n,m,k,s;
int a[N];
int d[N],q[N];
int ans[N][110]; //ans[i][j]表示第j种干草到点i的最短距离
int h[N],e[M],ne[M],idx;void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void bfs(int type)
{memset(d,0x3f,sizeof d);int hh=0,tt=-1;for(int i=1;i<=n;i++)if(a[i]==type)q[++tt]=i,d[i]=0; //多源bfs,会有多个起点while(hh<=tt){auto t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]>d[t]+1){d[j]=d[t]+1;q[++tt]=j;}}}for(int i=1;i<=n;i++){ans[i][type]=d[i];}}
int main()
{cin>>n>>m>>k>>s;for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(h,-1,sizeof h);for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);add(u,v),add(v,u);}//对于每一种干草跑一边多源bfs,记录每一种干草到各个点的最短距离for(int i=1;i<=k;i++)bfs(i);//对于每一个点需要拿到距离最短的s种干草的距离，所以这里进行排序for(int i=1;i<=n;i++)sort(ans[i]+1,ans[i]+1+k);for(int i=1;i<=n;i++){LL res=0;for(int j=1;j<=s;j++)res+=ans[i][j]; printf("%lld ",res);}return 0;
}这篇关于Acwing 5475. 聚会【多源bfs】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
