题目描述

CSU镇上有n个商店，n个商店有m条双向小路相连，在这n个商店里共有k种不同商品，每个商店只有一种商品，每条路的权重都为1。现问你从每个商店出发，买够k种商品中的s种商品所需的最小代价,每个商店可以同时派出多个人买不同商品，买够即可。

输入格式

1
2
3
4
5
输入包含多组测试用例。 
对于每一组输入包含四个数字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之间有小路连接。

输出格式

1
输出n个数字，第i个数字代表从商店i出发买够s种商品所需的最小代价。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

输出样例

1
2
2 2 2 2 3 
1 1 1 2 2 1 1

很明显是道 bfs , 但是要跑 n 遍 bfs ？ 考虑到数据 1e5 ,显然要超时的。。多源 bfs 常见处理就是，把一些点一起压入队列跑 bfs,避免频繁跑 bfs。题目要求的是，每一个点跑够 s 个不同的商品，点很多，而商品很少，所以可以先求每个商品到各个点的最小距离，这样一次可以将多个点（同商品）压入队列中，符合上面提到的处理方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int MAX=100000+10;
int  n,m,k,s,x,y,a[MAX],dis[MAX][105];
struct edge{
    int to,next;
}e[MAX*2] ;
int h[MAX],tot=0;
void addedge(int u,int v){
    e[tot].to=v;
    e[tot].next=h[u];
    h[u]=tot++;
}
int  bfs(int x){
    queue<int>q;
    fi(i,1,n+1)
        if(a[i] == x) {
            q.push(i);
            dis[i][x]=0;
        }
    while(!q.empty()){
        int t=q.front();
        q.pop(); 
        for(int i=h[t];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(dis[v][x]==-1){
                dis[v][x]=dis[t][x]+1;
                q.push(v);
            }
        } 
    }
}
int main(){
//  freopen("in","r",stdin);
    while(~sf(n)){
        sf(m);sf(k);sf(s);
        fi(i,1,n+1)
            sf(a[i]);
        mem(h,-1);
        mem(dis,-1);
        fi(i,0,m){
            sf(x);sf(y);
            addedge(x,y);addedge(y,x);
        }
        fi(i,1,k+1)
            bfs(i);
        fi(i,1,n+1){
            sort(dis[i]+1,dis[i]+1+k);
            int cnt=0;
            fi(j,1,s+1){
                cnt += dis[i][j];
            }
            pf(cnt);pfc(" ");
        }
        pfc("\n");
    }
    return 0;
}