哦!请问哪里有错

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int b[110][20],f[110][20],p[110];
int d[300000][20]={0};
int dist[32900];
int st[20],inque[32900]={0};
int ans=99999999,finish;
bool isok(int a[][20],int tmp,int en){
    int i;
    for(i=1;i<=m;i++){
        if(b[en][i]!=0){
            if(a[tmp][i]==0&&b[en][i]==-1) return 0;
            else if(a[tmp][i]==1&&b[en][i]==1) return 0;
        }
    }
    return 1;
}
int Ha_sh(int a[]){
    int i,x=1,s=0;
    for(i=1;i<=n;i++){
        s+=a[i]*x;
        x*=2;
    }
    return s;
}
void bfs(){
    int i,j,head=1,tail=2,tmp;
    inque[0]=1;
    finish=(1<<n)-1;
    d[1][0]=0;
    while(head<tail){
        int y=Ha_sh(d[head]);
        for(i=1;i<=m;i++){
            if(!isok(d,head,i)) continue;
            for(j=1;j<=n;j++){
                if(f[i][j]==-1) st[j]=1;
                else if(f[i][j]==1) st[j]=0;
                else if(f[i][j]==0) st[j]=d[head][j];
            }
            int x=Ha_sh(st);
            tmp=dist[y]+p[i];
            if(tmp>ans) continue;
            if(tmp<dist[x]){
                for(j=1;j<=n;j++){
                    d[tail][j]=st[j];
                }
                dist[x]=tmp;
                if(!inque[x]){
                    inque[x]=1;
                    tail++;
                }
            }
            if(inque[finish]) ans=min(ans,tmp);
        }
        inque[y]=0;
        head++;
    }
    if(ans!=99999999) cout<<ans;
    else cout<<"0";
    return;
}
int main(){
    //freopen("in.txt","r",stdin);
    int i,j;
    char a;
    scanf("%d %d",&n,&m);
    int x=(1<<n)-1;
    for(i=1;i<=x;i++){
        dist[i]=99999999;
    }
    for(i=1;i<=m;i++){
        scanf("%d",&p[i]);
        for(j=1;j<=n;j++){
            cin>>a;
            if(a=='+') b[i][j]=1;
            if(a=='-') b[i][j]=-1;  
            if(a=='0') b[i][j]=0;
        }
        for(j=1;j<=n;j++){
            cin>>a;
            if(a=='+') f[i][j]=1;
            if(a=='-') f[i][j]=-1;  
            if(a=='0') f[i][j]=0;
            }
    }
    bfs();
    return 0;
}

1 条评论

  • 1

信息

ID
1019
难度
6
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
1524
已通过
461
通过率
30%
被复制
1
上传者