nangcapmaytinh

 avatar
duyvan
plain_text
17 days ago
1.6 kB
4
Indexable
Never
#include<iostream>
using namespace std;
// code 100/100
int tc,n,slggoi,gia[20],goi[30][23], can[20],slgcan;
int visited[21],minn;

bool checkgoi(int m, int i){
    for(int j=0;j<goi[i][1];j++){
        if(goi[i][j+2]==m) return true;
    }
    return false;
}
void BT(int st,int sum){
    if(st==slgcan){
        if(sum<minn){
            minn=sum;
            return;
        }
    }
    if(sum>=minn) return;
    if(visited[can[st]]>=1){
        BT(st+1,sum);
    }
    else{
        visited[can[st]]++;
        BT(st+1,sum+gia[can[st]-1]);
        visited[can[st]]--;
        for(int i=0;i<slggoi;i++){
            if(checkgoi(can[st],i) ){
                for(int j=0;j<goi[i][1];j++){
                    visited[goi[i][2+j]]++;
                }
                BT(st+1,sum+goi[i][0]);
                for(int j=0;j<goi[i][1];j++){
                    visited[goi[i][2+j]]--;
                }
            }
        }
    }
}
int main(){
    freopen("input.txt","r",stdin);
    cin>>tc;
    for(int t=1;t<=tc;t++){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>gia[i];
        }
        cin>>slggoi;
        for(int i=0;i<slggoi;i++){
            cin>>goi[i][0]>>goi[i][1];
            for(int j=0;j<goi[i][1];j++){
                cin>>goi[i][2+j];
            }
        }
        cin>>slgcan;
        for(int i=0;i<slgcan;i++){
            cin>>can[i];
        }

        minn=987654321;
        BT(0,0);
        cout<<"#"<<t<<" "<<minn<<endl;
    }
    return 0;
}

Leave a Comment