二进制储存状态+spfa
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int b1[102],b2[102],f1[101],f2[102];
int cost[102];
char in[102];
queue<int>q;
bool inque[1048577];
int dis[1048577];
int main()
{
cin.sync_with_stdio(false);
int n,m;
cin>>n>>m;
if(n==0)
{
//printf("0");
cout<<"0";
return 0;
}
int base,len;
for(int i=1;i<=m;i++)
{
cin>>cost[i];
base=1;
cin>>in;
for(int j=0;in[j]!=' ';j++)
{
switch(in[j])
{
case '+':b1[i]+=base;break;
case '-':b2[i]+=base;break;
case '0':break;
}
base*=2;
}
base=1;
cin>>in;
for(int j=0;in[j]!=' ';j++)
{
switch(in[j])
{
case '-':f1[i]+=base;break;
case '+':f2[i]+=base;break;
case '0':break;
}
base*=2;
}
}
base=1;
int begin=0;
for(int i=1;i<=n;i++)
{
begin+=base;
base*=2;
}
for(int i=0;i<=begin;i++)
dis[i]=0x7ffffff;
q.push(begin);
dis[begin]=0;
inque[begin]=true;
int pass,nxt;
while(!q.empty())
{
pass=q.front();
q.pop();
inque[pass]=false;
for(int i=1;i<=m;i++)
{
if((pass&b1[i])!=b1[i])
continue;
if((pass&b2[i])!=0)
continue;
int ha=pass&f1[i];
nxt=pass-ha;
nxt=nxt|f2[i];
if(dis[nxt]<dis[pass]+cost[i])
continue;
dis[nxt]=dis[pass]+cost[i];
q.push(nxt);
if(!inque[nxt])
inque[nxt]=true;
}
}
//printf("%d",dis[0]);
cout << (dis[0] ==0x7ffffff?0:dis[0])<<endl;
}