Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.4 kB
1
Indexable
Never
ll rec(string &t,string mk,ll cost,ll bag,vector<vector<string>>&arr,unordered_map<pair<string,ll>,ll>&dp){
    //cout<<mk<<"\n";
    if(mk==t) return cost;
    if(dp.find({mk,bag})!=dp.end()) return dp[{mk,bag}];

    if(bag>=arr.size() || mk.size()>t.size()) return INT_MAX;

    ll op=INT_MAX,cl=INT_MAX;
    cl=rec(t,mk,cost,bag+1,arr,dp); //dont open this bag
    for(string x:arr[bag]){ //open this bag and choose one x
        string nk=mk+x;
        op=min(op,rec(t,nk,cost+1,bag+1,arr,dp));
    }
    return dp[{mk,bag}]=min(op,cl);
}

void solve(){
    string t;cin>>t;
    ll n;cin>>n;
    vector<vector<string>>arr;
    while(n--){
        ll a;cin>>a;
        vector<string>tmp;
        while(a--){
            string in;cin>>in;
            tmp.pb(in);
        }
        arr.pb(tmp);
    }

//    for(ll i=0;i<arr.size();i++) {
//        cout<<i<<"-";
//        for(auto j:arr[i]){
//            cout<<j<<" ";
//        }
//        cout<<"\n";
//    }
    ll bg=arr.size();
    //vector<vector<ll>>dp(bg, vector<ll>(1000, -1));
    unordered_map<pair<string,ll>,ll>dp;
    //dp[t]=0;
    ll res=rec(t,"",0,0,arr,dp);
    cout<<((res==INT_MAX)?-1:res)<<"\n";
}


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll t=1;
	//cin>>t;
	while(t--) solve();
}
Leave a Comment