[Uva658] It's not a Bug, it's a Feature!
题目略 UVA658 Problem PDF上有
试题分析：
本题可以看到：有<=20个潜在的BUG，那么如果每一个补丁都DFS一下的话肯定炸掉，那么怎么办呢？
我们发现，要在一个最短的时间求出来，而且状态之间可以变换多次，那么DP呢？
DP的话，由于BUG指令可以用0代替，所以我们无从转移，也就是说有后效性(后面的决策可能影响前面的)
那么还有什么此类转移的算法呢？貌似只剩下图论了……
对于每一个补丁之前的样子中的0，我们可以直接枚举(DFS)，将它转换为一些2进制数连边建图，然后跑一遍最短路就可以啦。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
//#include<cmath>
using namespace std;
const int INF = 9999999;
#define LL long long
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
int N,M;int t;
char str1[101],str2[101];
int len;char str[101];
int cnt;int Node[3000100],Next[3000100],Root[3000100],Cost[3000100];
int dis[3000100];bool inq[3000100];
int que[3001000];
void add(int u,int v,int w){
cnt++;
Node[cnt]=v;
Cost[cnt]=w;
Next[cnt]=Root[u];
Root[u]=cnt;
return ;
}
void addedge(int sum,int sum2,int k){//将每一个补丁转换为2进制数，将前后状态连边
if(k==len){
add(sum,sum2,t);
return ;
}
if(str2[k]!='0'){
if(str2[k]=='+'){
if(str[k]=='0'){
addedge(sum+(1<<k),sum2+(1<<k),k+1);
addedge(sum,sum2+(1<<k),k+1);
}
else{
if(str[k]=='-') addedge(sum,sum2+(1<<k),k+1);
else addedge(sum+(1<<k),sum2+(1<<k),k+1);
}
return ;
}
else{
if(str[k]=='0'){
addedge(sum+(1<<k),sum2,k+1);
addedge(sum,sum2,k+1);
}
else{
if(str[k]=='-') addedge(sum,sum2,k+1);
else addedge(sum+(1<<k),sum2,k+1);
}
return ;
}
}
else{
if(str[k]=='0'){
addedge(sum+(1<<k),sum2+(1<<k),k+1);
addedge(sum,sum2,k+1);
return ;
}
else
if(str[k]=='-') addedge(sum,sum2,k+1);
else addedge(sum+(1<<k),sum2+(1<<k),k+1);
}
return ;
}
int SPFA(int s,int t){
memset(dis,INF,sizeof(dis));
memset(inq,false,sizeof(inq));
dis[s]=0; inq[s]=true; int tail=1; que[tail]=s;
for(int head=1;head<=tail;head++){
for(int x=Root[que[head]];x;x=Next[x]){
if(dis[Node[x]]>dis[que[head]]+Cost[x]){
dis[Node[x]]=dis[que[head]]+Cost[x];
if(!inq[Node[x]]){
inq[Node[x]]=true;
que[++tail]=Node[x];
}
}
}
inq[que[head]]=false;
}
return dis[t];
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
N=read(),M=read();
for(int i=1;i<=M;i++){
t=read();
cin>>str>>str2;
len=strlen(str);
addedge(0,0,0);
}
printf("%d
",SPFA((1<<N)-1,0));
return 0;
}