CF1846G AC

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;
using b10s = bitset<10>;

b10s getset(const string &s)
{
    assert(s.size() <= 10);
    int res = 0;
    for (int i = 0; i < s.size(); ++i)
        res = (res << 1) | s[i] == '1';
    return b10s(res);
}

int dijkstra(const vector<string> &in, const vector<string> &out, const vi &ds, int start, int dest)
{
    int n = in[0].size(), m = in.size();
    vi dist(1 << (n + 1), INT_MAX / 2);
    dist[start] = 0;
    dbg(start, dest);
    vector<int> ind(m), outd(m);
    auto f = [](const string &s) { return (int) getset(s).to_ullong(); };
    transform(in.begin(), in.end(), ind.begin(), f);
    transform(out.begin(), out.end(), outd.begin(), f);
    set<int> vis;
    mpq<pii> pq;
    pq.push({0, start});
    while (pq.empty() == false) {
        auto [d, u] = pq.top();
        pq.pop();
        if (vis.count(u))
            continue;
        vis.insert(u);
        dist[u] = min(dist[u], d);

        for (int i = 0; i < m; ++i) {
            int v = (u & ~ind[i]) | outd[i];
            if (dist[v] > d + ds[i]) {
                dist[v] = d + ds[i];
                pq.push({dist[v], v});
            }
        }
    }

    return INT_MAX / 2 == dist[dest] ? -1 : dist[dest];
}

int main(int argc, char **argv)
{
    int t, n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        string start;
        cin >> start;
        vi ds(m);
        vector<string> in(m), out(m);
        for (int i = 0; i < m; ++i)
            cin >> ds[i] >> in[i] >> out[i];

        int ans = dijkstra(in, out, ds, (int) getset(start).to_ullong(), 0);
        cout << ans << endl;
    }
    return 0;
};