R485(Div.2) D. Fair

정점과 간선이 n,m(<=100000)개 들어오고 가중치 s(<=k)가 들어온다.

그리고 정점에서 k개의 다른 가중치를 들고있게 만들어야한다.

그때 비용은 정점간의 거리다!

간선 가중치가 다 1이므로 bfs를 돌리면 된다.

처음에 100000개 정점에서 다 돌리려고 했는데 그럼 시간초과난다 ㅎㅎ

거꾸로 생각해서 가중치가 100 이하이므로

가중치로 dfs를 최대 100번 돌리면 된다.

d[MAX_N][가중치]로 테이블을 잡고 각 가중치에서 정점으로 가는 최단거리를 찾는다. 

테이블을 다 채우고 비용이 낮은 순부터 k개를 더하면 k개의 서로 다른 가중치를 갖는 최소한의 비용이 된다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAX_N 100010
int n, m, s, k;
int cost[MAX_N], d[MAX_N][111];
vector<int> Graph[MAX_N], cGraph[111];
 
void dfs(int x) {
    queue<int> q;
    for (int y : cGraph[x]) {
        d[y][x] = 0;
        q.push(y);
    }
    while (!q.empty()) {
        int pos = q.front();
        q.pop();
 
        for (int y : Graph[pos]) {
            if (d[y][x] == -1) {
                d[y][x] = d[pos][x] + 1;
                q.push(y);
            }
        }
    }
}
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d %d %d %d", &n, &m, &s, &k);
    for (int i = 0; i < n; i++) {
        scanf(" %d", &cost[i]);
        cGraph[cost[i]].push_back(i);
    }
 
    for (int i = 0; i < m; i++) {
        int x, y; scanf(" %d %d", &x, &y);
        x--; y--;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }
 
    for (int i = 1; i <= s; i++) dfs(i);
    for (int i = 0; i < n; i++) {
        vector<int> pvt;
        for (int j = 1; j <= s; j++) pvt.push_back(d[i][j]);
        sort(pvt.begin(), pvt.end());
        int ans = 0;
        for (int q = 0; q < k; q++) ans += pvt[q];
        printf("%d ", ans);
    }
}