http://acm.hdu.edu.cn/showproblem.php?pid=4536
细节很重要呀 一个小的地方错了 检查了N久呀 鄙视自己
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int MOD=1000000007;
const int N=105;
const int M=5000005;
struct node
{
char dread[20];
char M;
}q[M];
int f[20];
int k1[N],k2[N],k3[N];
int ans,cnt;
int n,m,k;
int qt[M],L,R;
int bfs(char *dread)
{
for(int i=0;i<n;++i)
q[cnt].dread[i]=dread[i];
q[cnt].M=0;
L=R=0;
qt[R++]=cnt++;
int l=0,W;
while(L<R)
{
int x=qt[L++];
l=q[x].M;
if(l==k) return l;
if(cnt>=M) continue;
W=1;
q[cnt].M=q[x].M+1;
for(int i=0;i<n;++i)
{
if(i==k1[l+1])
q[cnt].dread[i]=max(q[x].dread[i]-2,1);
else if(i==k2[l+1]||i==k3[l+1])
q[cnt].dread[i]=q[x].dread[i]+2;
else if(f[i]==f[k2[l+1]]||f[i]==f[k3[l+1]])
q[cnt].dread[i]=q[x].dread[i]+1;
else
q[cnt].dread[i]=q[x].dread[i];
if(q[cnt].dread[i]>W)
W=q[cnt].dread[i];
if(W>5) break;
}
if(W<=5)
qt[R++]=cnt++;
if(cnt>=M) continue;
W=1;
q[cnt].M=q[x].M+1;
for(int i=0;i<n;++i)
{
if(i==k2[l+1])
q[cnt].dread[i]=max(q[x].dread[i]-2,1);
else if(i==k1[l+1]||i==k3[l+1])
q[cnt].dread[i]=q[x].dread[i]+2;
else if(f[i]==f[k1[l+1]]||f[i]==f[k3[l+1]])
q[cnt].dread[i]=q[x].dread[i]+1;
else
q[cnt].dread[i]=q[x].dread[i];
if(q[cnt].dread[i]>W)
W=q[cnt].dread[i];
if(W>5) break;
}
if(W<=5)
qt[R++]=cnt++;
if(cnt>=M) continue;
W=1;
q[cnt].M=l+1;
for(int i=0;i<n;++i)
{
if(i==k3[l+1])
q[cnt].dread[i]=max(q[x].dread[i]-2,1);
else if(i==k2[l+1]||i==k1[l+1])
q[cnt].dread[i]=q[x].dread[i]+2;
else if(f[i]==f[k2[l+1]]||f[i]==f[k1[l+1]])
q[cnt].dread[i]=q[x].dread[i]+1;
else
q[cnt].dread[i]=q[x].dread[i];
if(q[cnt].dread[i]>W)
W=q[cnt].dread[i];
if(W>5) break;
}
if(W<=5)
qt[R++]=cnt++;
}
return l;
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
for(int w=1;w<=T;++w)
{
printf("Case #%d: ",w);
char dread[20];
scanf("%d %d %d",&n,&m,&k);
for(int i=0;i<n;++i)
scanf("%d",&f[i]);
for(int i=0;i<n;++i)
scanf("%d",&dread[i]);
for(int i=1;i<=k;++i)
scanf("%d %d %d",&k1[i],&k2[i],&k3[i]);
ans=0;
cnt=0;
printf("%d\n",bfs(dread));
}
return 0;
}
