nangcapmaytinh
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