SP 2 cpp

#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;

template <typename T>
class Automata{
    public:
        int A;
        T s;
        vector<T> S;
        vector<T> F;
        map<pair<T , char> , T> f;
        map<pair<T , T> , char> inverse_f;

    Automata(int _A , vector<T> _S , T _s  , vector<T> _F , map<pair<T , char> , T >  _f){
        A = _A;
        s = _s;
        S = _S;
        F = _F;
        f = _f;
        for(typename map<pair<T , char> , T >::iterator it = f.begin() ; it != f.end(); ++it)
            inverse_f[{it->fi.fi , it->se}] = it->fi.se;
    //  cout << "f(" << it->fi.fi << " , " << it->fi.se << ") = " << it->second << nl;

    }

    private: T bfs(map<T , int> &d , map<T , T> & p , map<T , bool> & used){
        queue<T> q;
        q.push(s);
        used[s] = 1;
        p[s] = NULL;
        T ret = NULL;
        while(sz(q)){
            T v = q.front();
            q.pop();
            for(char c = 'a' ; c < A + 'a' ; ++c){
                if(f.find({v , c}) != f.end()){
                    T to = f[{v , c}];
                    if(!used[to]){
                        used[to] = 1;
                        q.push(to);
                        d[to] = d[v] + 1;
                        p[to] = v;
                        if(find(F.begin(), F.end(), to)!= F.end()){
                            ret = to;
                            cout << "We have found a finish vertex!" << nl;
                        }
                    }
                }
            }
        }
        return ret;
    }

    public: vector<T> Solve_10(){
        map<T , int> d;
        map<T , T> p;
        map<T , bool> used;
        T need = bfs(d , p , used);
        vector<T> path;
        if (need == NULL)
            cout << "No word!";
        else{
            for (T v=need; v!=NULL; v=p[v])
                path.push_back (v);
            path.pb(s);
            reverse (path.begin(), path.end());
        /*  cout << "Word: ";
            for (size_t i=0; i<path.size()-1; ++i)
                cout << a1.inverse_f[{path[i] , path[i + 1]}] << " ";*/
        }
        return path;
    }

    public: Automata<pair<T , T> > Multiply (Automata<T> a , Automata<T> b){
        int new_A = max(a.A , b.A);
        vector<pair<T , T> > new_S;
        for(int i = 0 ; i < sz(a.S) ; ++i){
            for(int j = 0 ; j < sz(b.S) ; ++j){
                new_S.pb({a.S[i] , b.S[j]});
            }
        }
    /*  for(T a.S: i){
            for(T b.S : j){
                new_S.pb({i , j});
            }
        }*/
        pair<T , T> new_s = {a.s , b.s};
        vector<pair<T , T> > new_F;
        for(int i = 0 ; i < sz(a.F) ; ++i){
            for(int j = 0 ; j < sz(b.F) ; ++j){
                new_S.pb({a.F[i] , b.F[j]});
            }
        }
        map<pair<pair<T , T> , char> , pair<T , T> > new_f;

        for(char c = 'a' ; c < 'a' + new_A ; ++c){
            for(pair<T , T> i : new_S){
                if(a.f.find({i.fi , c}) != a.f.end() && b.f.find({i.se , c}) != b.f.end()){
                    new_f[{i , c}] = { a.f[{i.fi , c}] , b.f[{i.se , c}] };
                }
            }
        }
        Automata<pair<T , T> > res = Automata<pair<T , T> >(new_A , new_S , new_s , new_F , new_f);
        return res;
    }

};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(0);
    int A;
    int S1;
    int s;
    cin >> A >> S1 >> s;
    vi S(S1 , 0);
    rep(i , S1)S[i] = i;
    int t;
    cin >> t;
    vi F(t , 0);
    rep(i , t)cin >> F[i];
    map<pair<int , char> , int>  f;
    cin >> t;
    rep(i , t){
        int u , v;
        char a;
        cin >> u >> a >> v;
        f[{u , a}] = v;
    }
    Automata<int> a1 = Automata<int>(A , S , s , F , f);

    for(char ch = 'a' ; ch < 'a' + a1.A ; ++ch)cout  << ch << " ";
    cout << nl;
    for(int i : a1.S)cout << i << " ";
    cout << nl;
    cout << a1.s << nl;
    for(int i : a1.F)cout << i << " ";
    cout << nl;
    for (map<pair<int , char> , int>::iterator it = a1.f.begin() ; it != a1.f.end(); ++it)
        cout << "f(" << it->fi.fi << " , " << it->fi.se << ") = " << it->second << nl;

/*  queue<int> q;
    q.push(s);
//  vector<bool> used(1000 , 0);
    map<int , bool> used;
    used[s] = 1;
//  vi d(1000) , p(1000);
    map<int , int> d , p;
    p[s] = -1;
    int final = -1;
    while(sz(q)){
        int v = q.front();
        q.pop();
        for(char c = 'a' ; c < a1.A + 'a' ; ++c){
            if(a1.f.find({v , c}) != a1.f.end()){
                int to = a1.f[{v , c}];
                if(!used[to]){
                    used[to] = true;
                    q.push(to);
                    d[to] = d[v] + 1;
                    p[to] = v;
                    if(find(a1.F.begin(), a1.F.end(), to)!= a1.F.end()){
                        final = to;
                        cout << "We have found a finish vertex!" << nl;
                    }
                }
            }
        }
    }
    cout << d[final] << nl;
    if (!used[final])
        cout << "No word!";
    else{
        vector<int> path;
        for (int v=final; v!=-1; v=p[v])
            path.push_back (v);
        reverse (path.begin(), path.end());
        cout << "Word: ";
        for (size_t i=0; i<path.size()-1; ++i)
            cout << a1.inverse_f[{path[i] , path[i + 1]}] << " ";
    }*/
    vector<int> path= a1.Solve_10();
    for (size_t i=0; i<path.size()-1; ++i)
            cout << a1.inverse_f[{path[i] , path[i + 1]}] << " ";
    return 0;
}
/*
2
3
0

1 2
4
0 a 1
1 a 2
0 b 2
1 b 2


3
6
0

1 5
9
0 b 2
0 a 1
1 b 3
2 a 3
3 a 4
3 b 0
4 a 2
4 c 5
4 b 1
*/