F. Berland and the Shortest Paths | Codeforces Round #496 (Div. 3)

単一始点最短経路問題で、すべての頂点に最短で到達するのに必要な辺だけを選ぶと木になることが知られている(最短経路木)。

なので、この問題では最短経路木を列挙すればいいことがわかる。根でない頂点vに最短距離で到達した時、直前の頂点をuとする。d(x)を頂点xまでの最短距離とすると、d(u) + 1 = d(v)かつ辺(u, v)が存在するならば、どの辺(u, v)を使ってもよい。必要な分だけ別の辺を使えばいい。

int N, M, K;
vector<string> ans;
void f(int u, vector<vi> &cand, string &re, vi &U, vi &V) {
    if (u == N) {
        ans.push_back(re);
        return;
    }
    if (sz(cand[u])==0) {
        f(u + 1, cand, re, U, V);
    }
    each(e, cand[u]) {
        int v = U[u] ^ V[v] ^ u;
        re[e] = '1';
        f(u + 1, cand, re, U, V);
        re[e] = '0';
        if (sz(ans) == K)return;
    }
}

int main() {
    cin >> N >> M >> K;

    vector<vi> G(N);
    vi U(M), V(M);
    rep(i, M) {
        cin >> U[i] >> V[i];
        --U[i]; --V[i];
        G[U[i]].push_back(i);
        G[V[i]].push_back(i);
    }

    vi D(N, INT_MAX/2);
    D[0] = 0;
    queue<int> Q;
    Q.push(0);
    vector<vi> cand(N);
    vi vis(N);
    while (sz(Q)) {
        int u = Q.front();
        Q.pop();
        each(e, G[u]) {
            int v = u ^ U[e] ^ V[e];
            if (D[u] + 1 <= D[v]) {
                if (D[u] + 1 < D[v])Q.push(v);
                D[v] = D[u] + 1;
                cand[v].push_back(e);
            }
        }
    }

    string temp(M, '0');
    f(0, cand, temp, U, V);

    cout << sz(ans) << endl;
    each(re, ans)cout << re << endl;
}