有n个商店，n个商店有m条双向小路相连，在这n个商店里共有k种不同商品，每个商店只有一种商品，每条路的权重都为1。现问你从每个商店出发，买够k种商品中的s种商品所需的最小代价,每个商店可以同时派出多个人买不同商品，买够即可。
输入
对于每一组输入包含四个数字n ,m, k,s (1<=n<=m<=1e5 , 1<=s<=k<=min(n,100))
分别代表商店数，小路数，商品种数，需要的商品数。
接下来n个数 a1,a2…an (1<=ai<=k),ai代表第i个商店的商品编号。
接下来m行小路(u,v),u≠v,代表商店u和v之间有小路连接。
输出
输出n个数字，第i个数字代表从商店i出发买够s种商品所需的最小代价。
样例输入
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
样例输出
2 2 2 2 3
1 1 1 2 2 1 1
bfs+贪心
分析：N是1e5，直接对每个点搜肯定超时。而K的范围很小，而且1-K全部覆盖。对所有1-K的值BFS，用二维数组dp[i][j]记录i点要获取编号为j的物品最少走过的路程，并对每个点取最小的S个物品对应的路径。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn =1e5+5;
int a[maxn];
int ans[maxn];
vector<int> G[maxn];
bool vis[maxn];
int d[maxn][305];void BFS(int val,int N){memset(vis,0,sizeof(vis));queue<int> Q;for(int i=1;i<=N;++i){if(a[i]==val){vis[i]=true;Q.push(i);}}while(!Q.empty()){int x =Q.front();Q.pop();for(int i=0;i<G[x].size();++i){int v = G[x][i];if(!vis[v]){vis[v] = true;d[v][val] = d[x][val]+1;Q.push(v);}}}
}int main(){int N,M,K,S,u,v;while(scanf("%d%d%d%d",&N,&M,&K,&S)!=EOF){for(int i=1;i<=N;++i) G[i].clear();memset(d,0,sizeof(d));for(int i=1;i<=N;++i) scanf("%d",&a[i]);for(int i=1;i<=M;++i){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}for(int i=1;i<=K;++i){memset(vis,0,sizeof(vis));BFS(i,N);}for(int i=1;i<=N;++i){sort(d[i]+1,d[i]+K+1);ans[i]=0;for(int j =1;j<=S;++j){ans[i]+=d[i][j];}}for(int i=1;i<N;++i) printf("%d ",ans[i]);printf("%d\n",ans[N]);}return 0;
}