多源bfs+贪心
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10,M=2*N,INF=0x3f3f3f3f;
int n,m,k,s;
int q[N];
int dist[N];
int h[N],e[M],ne[M],id[N],idx;
int w[N][110];//表示第i个谷仓到第j种干草的最短距离,遍历所有的谷仓求所有干草到谷仓的最短
void add(int a,int b)//距离会tle,反过来求所有谷仓到干草的最短路
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void bfs(int num)
{
int hh=0,tt=-1;
memset(dist,0x3f,sizeof dist);//必须初始化为无穷而不是-1
for(int i=1;i<=n;i++)//防止最短距离为-1扰乱后面排序的结果
if(id[i]==num)
{
q[++tt]=i;
dist[i]=0;
}
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(dist[j]==INF)//第一次扩展到的点必然是最短的,因此被扩展过就不用再更新了
{
dist[j]=dist[t]+1;
q[++tt]=j;
}
}
}
for(int i=1;i<=n;i++)
w[i][num]=dist[i];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&s);//数据量大采用scanf,printf
for(int i=1;i<=n;i++)
scanf("%d",&id[i]);
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
for(int i=1;i<=k;i++)//枚举所有干草,求得所有仓谷到此干草的最短距离
bfs(i);
for(int i=1;i<=n;i++)
{
sort(w[i]+1,w[i]+k+1);//则最小的运输成本就是前s个最短距离之和
int res=0;
for(int j=1;j<=s;j++)
res+=w[i][j];
printf("%d ",res);
}
return 0;
}