题解：CF1846G Rudolf and CodeVid-23

_Weslie_ · 2025-06-22 20:36:47 · 题解

Solution CF1846G

Idea

注意到 n\le 10，这启示我们状压，毕竟最多只有 2^{10}=1024 种状态。

然后最短路转移就枚举初始状态 u，然后就考虑吃第 i 种药。第 i 种药会治好 x_i（其中 x_i 是一个二进制数，这一位是 1 代表可以治好）的病，产生 y_i（同 x_i）的副作用。

那么问题来了：末状态 v 是什么呢？

设 t 的反状态为：t 二进制下所有为 1 的位变为 0，0 的位变为 1。所以 t 的反状态 u=(2^n-1) \oplus t。

那么 x_i 的反状态 xx_i 就代表吃下药 i 之后无法治好的病。那么原先得的病，和无法治好的病取个并，就可以得到吃下药 i 产生副作用之前可以得到的病了。

至于副作用，与刚才的副作用之前的值或一下就行。这个理解起来很容易：只要这一个药可以产生，或者之前就得了，就会患。

然后枚举初状态 u，枚举药，按照上面算出末状态 v，然后跑最短路就行。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int get(string s){
    int res=0,t=1;
    for(int i=0;i<s.length();i++){
        res=res+t*(s[i]=='1');
        t<<=1;
    }
    return res;
}
int n,m,dis[1<<N],vis[1<<N];
string tmp;
struct node{
    int x,y,t;
}a[1005];
void solve(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<(1<<n);i++){
        dis[i]=0x3f3f3f3f;
        vis[i]=0;
    }
    cin>>tmp;
    dis[get(tmp)]=0;
    for(int i=1;i<=m;i++){
        cin>>a[i].t;
        cin>>tmp;
        a[i].x=get(tmp);
        cin>>tmp;
        a[i].y=get(tmp);
    }
    while(1){
        int u=-1;
        for(int i=0;i<(1<<n);i++){
            if(vis[i]||dis[i]==0x3f3f3f3f)continue;
            if(u==-1||dis[i]<dis[u]){
                u=i;
            }
        }
        if(u==-1)break;
        vis[u]=1;
        for(int i=1;i<=m;i++){
            int w=a[i].t;
            int v=(u&(((1<<n)-1)^a[i].x))|a[i].y;
            dis[v]=min(dis[v],dis[u]+w);
        }  
    }
    cout<<(dis[0]==0x3f3f3f3f ? -1 : dis[0])<<endl;
}
int main(){
    int T;cin>>T;
    while(T--)solve();
}