2481번: 해밍 경로

https://www.acmicpc.net/problem/2481


$O(nk\lg n+nm)$

각 수에 대해 한 자리씩 바꿔보면서 그래프를 형성한 다음, BFS를 돌리자. 처음 방문할 때까지 드는 비용이 최소 비용이다.

#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
const int MAX_N = 1e5;
int n, m, k, q[MAX_N], h, t, fr[MAX_N + 1], ck[MAX_N + 1];
map<int, int> mp;
vector<int> adj[MAX_N + 1];
void f(int x) {
    if (x != 1) f(fr[x]);
    printf("%d ", x);
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int t = 0;
        for (int j = 0, x; j < k; j++) scanf("%1d", &x), t += (1 << j)*x;
        mp[t] = i;
    }
    for (auto it : mp) {
        for (int i = 0; i < k; i++) {
            auto t = mp.find(it.first ^ (1 << i));
            if (t != mp.end()) adj[it.second].push_back(t->second);
        }
    }
    q[t++] = ck[1] = fr[1] = 1;
    while (h ^ t) {
        for (auto it : adj[q[h]]) {
            if (ck[it]) continue;
            q[t++] = it;
            fr[it] = q[h];
            ck[it] = 1;
        }
        h++;
    }
    scanf("%d", &m);
    for (int i = 0, x; i < m; i++) {
        scanf("%d", &x);
        fr[x] ? f(x), puts("") : puts("-1");
    }
    return 0;
}