分析：
这道题是今天的任务，受到的金币+30的诱惑，我就选择了这道题
真的怎么也没想到这是一道最短路
每使用一个补丁，就会达到一个状态，同时会消耗一定的时间
我们可以把不同的状态抽象成一个个的点，
每个点可以向ta的后继节点继续前进
这就相当于提问从起点到终点，经过若干操作，达到目标时的最小花费
这就是一个最短路模型
其实这也可以像bfs一样进行，但是因为有不同的花费，
所以要把所有的路径都搜出来，
那还不如我们把能够遍历到的所有状态一层一层的连起来，
跑一个最短路（最后还是转到了最短路上）
那我们就来说一下怎么建图吧:
用二进制存补丁的全部信息
我在代码中用了一些很zz的数组名称：
you[N],mei[N],xiu[N],chu[N] //有，没有，修复，出现
you数组存储该补丁使用时需要出现的漏洞，需要的状态是1
mei数组存储该补丁使用时不能出现的漏洞，不能出现的状态是1
xiu数组存储使用该补丁时修复的补丁，
这里要注意下，为了方便之后的计算，能够修复的状态是0，不能修复的状态是1
chu数组存储使用该补丁会引发的漏洞，出现的状态是1
具体计算
判断状态k，是否符合补丁i的使用条件：
(k&you[i])==you[j]&&(k&mei[i])==0
&:只有同是1的时候，值才为1
使用后的状态计算：
k=k|chu[j];
k=k&xiu[j];
|：只要一个是1，就是1
初始状态为2^n-1,末状态为0
跑最短路就好了
tip
只要是位运算，多加括号不是坏事
最短路我在这里选择的是spfa，如果用dij好像需要堆优化
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=102;
const int M=40000;
int n,m;
int T[N],you[N],mei[N],xiu[N],chu[N]; //有，没有，修复，出现
struct node{
int x,y,v,nxt;
};
node way[M<<4];
int st[M],tot=0,q[M],tou,wei,sta,dis[M];
bool p[M];
void add(int u,int w,int v)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].v=v;way[tot].nxt=st[u];st[u]=tot;
}
int spfa(int s,int t)
{
memset(dis,0x33,sizeof(dis));
memset(p,1,sizeof(p));
p[s]=0; dis[s]=0;
tou=wei=0;
q[++wei]=s;
do
{
int r=q[++tou];
for (int i=st[r];i;i=way[i].nxt)
if (way[i].v+dis[r]<dis[way[i].y])
{
dis[way[i].y]=way[i].v+dis[r];
if (p[way[i].y])
{
p[way[i].y]=0;
q[++wei]=way[i].y;
}
}
}
while (tou<wei);
if (dis[t]==0x33333333) return 0;
else return dis[t];
}
void doit()
{
int i,j;
for (i=1;i<=sta;i++)
for (j=1;j<=m;j++)
{
int k=i;
if ((k&you[j])==you[j]&&(k&mei[j])==0) //&都是1
{
k=k|chu[j]; //出现
k=k&xiu[j]; //xiu是反的，同1得1
add(i,k,T[j]);
}
}
printf("%d",spfa(sta,0));
}
int main()
{
scanf("%d%d",&n,&m);
char s[20];
sta=(1<<n)-1; //2^n-1; 1表示有该漏洞
for (int i=1;i<=m;i++)
{
scanf("%d",&T[i]);
scanf("%s",&s);
int num1=0,num2=0;
for (int j=0;j<n;j++)
{
num1<<=1; num2<<=1;
if (s[j]=='+') num1++;
if (s[j]=='-') num2++; //包含了Bi+中的所有错误, 而没有包含Bi-中的任何错误时
}
you[i]=num1; mei[i]=num2;
scanf("%s",&s);
num1=0,num2=0;
for (int j=0;j<n;j++)
{
num1<<=1; num2<<=1;
if (s[j]=='+') num1++;
if (s[j]=='-') num2++; //Fi-中的任何错误都不会在软件中出现，而软件将包含Fi+中的所有错误
}
xiu[i]=sta-num2; chu[i]=num1;
}
doit();
return 0;
}