BFS的WA*3
查看原帖
BFS的WA*3
633466
LiaoYF1楼主2023/1/22 19:02
#include<iostream>
#include<queue>
using namespace std;
int n,x,a[505],b[505];
bool f[1000005];
struct node{
    int now=0,c[55];
};
queue<node> q;
int main(){
    cin>>n>>x;
    node tmp;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        tmp.c[i]=b[i];
    }
    q.push(tmp);
    while(!q.empty()){
        node t=q.front();
        q.pop();
        if(t.now==x){
            cout<<"Yes";
            return 0;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=t.c[i];j++){
                if(!f[t.now+a[i]*j]){
                    f[t.now+a[i]*j]=1;
                    node sb=t;
                    sb.c[i]-=j;
                    sb.now=t.now+a[i]*j;
                    q.push(sb);
                }
            }
        }
    }
    cout<<"No";
    return 0;
}
2023/1/22 19:02
加载中...