A. Fair | Codeforces Round #485 (Div. 1)

各商品をスタート地点として見てBFSっぽいことをする。はじめにキューへすべての始点入れておくだけ。

int N, M, K, S;

vi G[100005];
int dis[100005][102];
vi pos[102];

void bfs(int kind) {
    queue<pii> Q;
    each(p, pos[kind]) {
        Q.push({ p,0 });
        dis[p][kind] = 0;
    }
    while (sz(Q)) {
        int u, d;
        tie(u, d) = Q.front();
        Q.pop();
        each(v, G[u]) {
            if (dis[v][kind] == -1) {
                dis[v][kind] = d + 1;
                Q.push({ v, d + 1 });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    MEM(dis, -1);
    cin >> N >> M >> K >> S;
    rep(a, N) {
        int kind;
        cin >> kind;
        pos[--kind].push_back(a);
    }
    rep(a, M) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    rep(a, K) {
        bfs(a);
    }
    rep(a, N) {
        sort(dis[a], dis[a] + K);
        int re = accumulate(dis[a], dis[a] + S, 0);
        cout << re << ' ';
    }
    cout << endl;
}