【最短路+状压】CF1846 G

Problem - G - Codeforces

题意：

思路：

Code：

#include <bits/stdc++.h>//#define int long longusing 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;
}