【最短路+状压】CF1846 G

叁歲伎倆 2024-03-17 18:16 43阅读 0赞

[Problem - G - Codeforces][]

题意：

![5f6c99eb4ebf41758b900d40bb638751.png][]

思路：

![b4b6e3ed9bcb46609c7c718e66098e81.png][]

Code：

#include <bits/stdc++.h>
     
    //#define int long long
     
    using namespace std;
     
    const int mxn=1e6+10;
    const int mxv=1e6+10;
    const int mxe=2e3+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    struct ty2{
        int x,dis;
        bool operator<(const ty2&a)const{
            return a.dis<dis;
        }
    };
    
    priority_queue<ty2> Q;
    
    int N,M,st=0;
    int d[mxn],e[mxn],se[mxn];
    int vis[(1<<10)+10],dis[(1<<10)+10];
    
    char x;
    
    void dij(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[st]=0;
        Q.push({st,0});
        while(!Q.empty()){
            auto u=Q.top();
            Q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=1;i<=M;i++){
                int w=d[i];
                int v=((u.x&(~e[i]))|se[i]);
                if(dis[v]>dis[u.x]+w){
                    dis[v]=dis[u.x]+w;
                    Q.push({v,dis[v]});
                }
            }
        }
    }
    void solve(){
    
        st=0ll;
        while(!Q.empty()) Q.pop();
    
        cin>>N>>M;
    
        for(int i=1;i<=M;i++){
            d[i]=e[i]=se[i]=0;
        }
        for(int i=0;i<N;i++){
            cin>>x;
            st|=((x=='1')<<i);
        }
        for(int i=1;i<=M;i++){
            cin>>d[i];
            e[i]=se[i]=0;
            for(int j=0;j<N;j++){
                cin>>x;
                e[i]|=((x=='1')<<j);
            }
            for(int j=0;j<N;j++){
                cin>>x;
                se[i]|=((x=='1')<<j);
            }
        }
        dij();
        if(dis[0]==Inf) cout<<-1<<'\n';
        else cout<<dis[0]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/contest/1846/problem/G
[5f6c99eb4ebf41758b900d40bb638751.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/662b082f67e9470dbac194c2c7272406.png
[b4b6e3ed9bcb46609c7c718e66098e81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ea713fa57270497d90cb5ab33bbb9aa6.png