G. Rudolf and CodeVid-23

题目链接：Problem - G - Codeforces

题目大意：

一种病有 n≤10 种症状。

一种病情可以用一个长度为 n 的01 串表示，其中第 i 个字符表示是否出现该种症状。

现有 m(∑m≤103) 种药，每种药用两个无交集的 01 串表示。第一个 01 串表示服用这种药物之后，串中被标记为 1 的症状将被消除。第二个 01 串表示，该药将产生副作用，将出现串中标记为 1 的症状。

每种药有一个服用疗程 d 天，上一种药的疗程没进行完时不能使用下一种药。

现给出初始病情，求最少需要几天可以消除所有症状。药可以重复使用。若不能则输出 −1.

第一行测试数据 组数 t≤100.

用到的算法与技巧： 最短路， 状态压缩， BFS， 图.

解题思路：由于看出给出的一个字符串长度不超过10， 可以将字符串压缩为一个整数（不会超过1024），所以将每一数看作为图上的一个结点，（起始字符串为起点）。然后通过bfs,进行搜索枚举每一种药物，检查最短路。 而最短路的 u到v 通过位运算实现。位运算实现如下  

int v = u &(~(g[i].u & u)) | g[i].v;  g[i].u 指的药物的第一行字符串&当前的 u 将可以消除的病状求出，取反再&u即可以得到消除病状过后的情况， 然后 | g[i].v,可得到产生副作用过后的情况。

代码实现：

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;

int go(string &s) { //状态压缩
    int res = 0;
    for(int i=s.size()-1,j = 0; i>=0; i--, j++) {
        res += (s[i] - '0') * (1<<j);
    }
    return res;
}
struct node{
    int wi;
    int u;
    int v;
};
const int N = 1200; //最大n==10, 1024 直接1200
void solve(){
    int n, m;
    cin >> n >> m;
    string s;
    cin  >> s;
    int suu = go(s); //找到起点
    vector<node> g(m+1);
    for(int i=1; i<=m; i++) {
        int d;
        string su, sv;
        cin >> d >> su >> sv;
        g[i].wi = d;
        g[i].u = go(su);
        g[i].v = go(sv);
    }

    vector<int>dis(N, INT_MAX);

    queue<int> q;
    q.push(suu);
    dis[suu] = 0;//做BFS
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=1; i<=m; i++) { //最短路的核心代码
            int v = u &(~(g[i].u & u)) | g[i].v;
            if(dis[u]+g[i].wi < dis[v]) {
                dis[v] = dis[u] + g[i].wi;
                q.push(v);
            }
        }
    }
    cout << (dis[0] == INT_MAX? -1 : dis[0]) << "\n";
    //判断是否到达到0，输出答案
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

感谢各位的观看与点赞， 欢迎大佬的指正。