题意：有n个bug，有m个补丁，每个补丁有一定的要求（比如某个bug必须存在，某个必须不存在，某些无所谓等等），打完出来后bug还可能变多了呢。但是打补丁是需要时间的，每个补丁耗时不同，那么问题来了：要打多久才能无bug？（同1补丁可重复打）
分析：
n<=20，那么用位来表示bug的话有220=100万多一点。不用建图了，图实在太大了，用位图又不好玩。那么直接用隐式图搜索（在任意点，只要满足转移条件，任何状态都能转）。
但是有没有可能每个状态都要搜1次啊？那可能是100万*100万啊，这样出题还有解么？大部分状态是怎么打补丁都到不了的，但是具体要说是多少个也不能这么说吧，这个分析可能也太麻烦了，设计100个补丁能将n个1打成所有状态都覆盖就差不多超时了。（出题人应该不会这么精明，忽略这个问题）
那么用位表示状态要怎么办？类似于状态压缩的感觉，每个bug有3种可能（必存在，必不存在，无所谓），只要40个位搞定，但是两个位表示1个bug状态也太麻烦了吧？那就开两个数组咯，配合表示就行了，丝毫没有省空间！！但是容易看了。但是这么设计使得在匹配的时候神速啊。
思路：
一开始所有bug是存在的，所以有sta=末尾n个1。接着我们要将其打成sta=0，任务艰巨，赶紧开始。
（1）首先求状态的上限up。将1左移n个位置再减少1。
（2）dijkstra来穷举每个状态，即0~up。用优先队列来优化它，一旦距离dist有更新，就进队(这么像SPFA!其实用了优先队列，一点不像，只要vis[该点]=1，那就忽略它，而spfa不忽略)。
（3）当队列不空一直循环，直到循环了up次，或者可达状态全部遍历过了，就退出了，直接检查dist[0]是否为无穷大。
难点：
其实这题考的不是SSSP，而是位运算的设计。
（1）如何检查m个bug种哪些是可以转移的？
数组pat_r1[i]表示第i个补丁需要哪些bug必须存在，存在则该位为1；
数组pat_r2[i]表示第i个补丁对那些bug无所谓，无所谓的位为0。
假设本状态为flag，判断第j个补丁是否可以打，应该这样：
int res=(flag^pat_r1[j]); //异或完，满足要求的(即相同的)位会为0（无所谓的先不管）。
res&=pat_r2[j]; //将无所谓的位全部置为0。
if(res==0) return true; //满足要求
（2）如何获取转移后的状态？
数组pat_o1[i]表示第i个补丁打完后输出的哪些bug依然存在，存在则该位为1；
数组pat_o2[i]表示第i个补丁打完后输出的哪些bug依然不变，不会变的位为1。
假设本状态为flag，打完补丁j 输出的结果应该是：
int tmp=(flag&pat_o2[j]); //将不变的取出来
tmp+=pat_o1[j]; //将不变的补回去
return tmp; //打完了
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=+;
const int INF=0x7f7f7f7f;
int pat_r1[N]; //补丁所需要的要求1
int pat_r2[N]; //补丁所需要的要求2，记录无所谓
int val[N]; //权值
int pat_o1[N]; //打完补丁后的产出1
int pat_o2[N]; //打完补丁后的产出2,记录不变
int dist[]; //表示状态
bool vis[];
int bugs, patches, v;
int res, tmp; //临时变量 /*
int cal() //超时！！未优化的dijkstra。
{
memset(dist,0x7f,sizeof(dist));
memset(vis,0,sizeof(vis)); int t=bugs, up=1;
while(t--) up+=up;
dist[--up]=0;
for(int i=up; i>=0; i--)
{
int small=INF, flag=INF;
for(int j=0; j<=up; j++) //在状态j中找dist最短
{
if(!vis[j]&&dist[j]<small)
{
flag=j; //标记该状态
small=dist[j]; //snall保存所耗时间
}
}
if(flag==INF) return -1; //找不到 vis[flag]=1; for(int j=1; j<=patches; j++) //扫描每个补丁
{
//检查是否满足条件
res=(flag^pat_r1[j]); //异或完，满足要求的会为0（除了无所谓的）。
res&=pat_r2[j]; //将无所谓的位全部置为0。 if( !res ) //只要为0就是满足条件
{
tmp=(flag&pat_o2[j]); //将不变的取出来
tmp+=pat_o1[j]; //将不变的补回去
if( dist[tmp]>dist[flag]+val[j] ) //时间比较短的
{
dist[tmp]=dist[flag]+val[j];
if(!tmp) return dist[tmp]; //bug全部修复
}
}
}
}
return -1; //修不了 } */ int can_use(int flag, int j)
{
//检查是否满足条件
int res=(flag^pat_r1[j]); //异或完，满足要求的会为0（除了无所谓的）。
res&=pat_r2[j]; //将无所谓的位全部置为0。
if(res==) return true;
return false;
} int get_sta(int flag, int j)
{
//获取将要更新的状态
int tmp=(flag&pat_o2[j]); //将不变的取出来
tmp+=pat_o1[j]; //将不变的补回去
return tmp;
} int cal()
{
priority_queue<pii, vector<pii>, greater<pii> > que; memset(vis, , sizeof(vis));
memset(dist, 0x7f, sizeof(dist)); int t=bugs, up=;
while(t--) up+=up; //获取上限
dist[--up]=; que.push(make_pair(,up));
while(!que.empty())
{
int flag=que.top().second; que.pop();
if(vis[flag]) continue; //重复
vis[flag]=; for(int j=; j<=patches; j++) //扫描每个补丁
{
int tmp=get_sta(flag, j);
if( can_use(flag, j) && dist[tmp]>dist[flag]+ val[j] ) //只要为0就是满足条件
{
dist[tmp]=dist[flag]+ val[j];
que.push(make_pair(dist[tmp],tmp));
}
}
}
return dist[];
} int main()
{
freopen("input.txt", "r", stdin);
char s[], s2[];
int Case=;
while(scanf("%d %d", &bugs, &patches ), bugs||patches)
{
for(int i=; i<=patches; i++)
{
scanf("%d %s %s", &v, s, s2);
val[i]=v;
pat_r1[i]= pat_r2[i]= ;
for(int j=; j<=bugs; j++) //要求
{
pat_r1[i]<<=;
pat_r2[i]<<=; if(s[j-]=='+') //'+'用1表示，'-'用0表示(直接移位，不用处理)
pat_r1[i]++;
if(s[j-]!='') //无所谓用0表示
pat_r2[i]++;
} pat_o1[i]= pat_o2[i]= ;
for(int j=; j<=bugs; j++) //输出
{
pat_o1[i]<<=;
pat_o2[i]<<=;
if(s2[j-]=='+') //有bug就1，无bug为0
pat_o1[i]++;
if(s2[j-]=='') //不变为1
pat_o2[i]++;
}
}
printf("Product %d\n",++Case);
int ans=cal();
if(ans<INF) printf("Fastest sequence takes %d seconds.\n\n", ans );
else printf("Bugs cannot be fixed.\n\n");
}
return ;
}
AC代码177ms
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=+;
const int INF=0x7f7f7f7f;
int pat_r1[N], pat_r2[N], pat_o1[N], pat_o2[N], val[N], dist[], vis[];
int bugs, patches, v; int can_use(int flag, int j)
{
int res=(flag^pat_r1[j]); //异或完，满足要求的会为0（除了无所谓的）。
res&=pat_r2[j]; //将无所谓的位全部置为0。
if(res==) return true;
return false;
} int get_sta(int flag, int j)
{
int tmp=(flag&pat_o2[j]); //将不变的取出来
tmp+=pat_o1[j]; //将不变的补回去
return tmp;
} int cal()
{
priority_queue<pii, vector<pii>, greater<pii> > que;
memset(vis, , sizeof(vis));
memset(dist, 0x7f, sizeof(dist));
int up=;
while(bugs--) up+=up;
dist[--up]=; que.push(make_pair(,up));
while(!que.empty())
{
int flag=que.top().second; que.pop();
vis[flag]=;
for(int j=; j<=patches; j++) //扫描每个补丁
{
int tmp=get_sta(flag, j);
if( can_use(flag, j) && dist[tmp]>dist[flag]+ val[j] ) //只要为0就是满足条件
{
dist[tmp]=dist[flag]+ val[j];
if(!vis[tmp]) que.push(make_pair(dist[tmp],tmp));
//if(!tmp) return dist[0]; //不能这么做，可能还有更新，这只是更新第一次而已，至少要n次
}
}
}
return dist[];
} int main()
{
freopen("input.txt", "r", stdin);
char s[], s2[];
int Case=;
while(scanf("%d %d", &bugs, &patches ), bugs||patches)
{
for(int i=; i<=patches; i++)
{
scanf("%d %s %s", &v, s, s2);
val[i]=v;
pat_r1[i]= pat_r2[i]= pat_o1[i]= pat_o2[i]= ;
for(int j=; j<=bugs; j++)
{
pat_r1[i]<<=,pat_r2[i]<<=,pat_o1[i]<<=,pat_o2[i]<<=;
if(s[j-]=='+') pat_r1[i]++;
if(s[j-]!='') pat_r2[i]++;
if(s2[j-]=='+') pat_o1[i]++;
if(s2[j-]=='') pat_o2[i]++;
}
}
int ans=cal();
if(ans<INF) printf("Product %d\nFastest sequence takes %d seconds.\n\n",++Case, ans );
else printf("Product %d\nBugs cannot be fixed.\n\n",++Case);
}
return ;
}
短码AC版本