Untitled

#define ll long long
// thios problem has a cycle so no DP 

struct cmp{
    bool operator() (const pair<ll,ll>a, const pair<ll,ll>b){
        return a.second >b.second;
    }
};
class Solution {
public:
    

    vector<ll> bfs(ll src,vector<vector<pair<ll,ll>>>&graph){
        vector<ll>distance(26,-1);
        distance[src]=0;
        priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
        pq.push({0,src});


        while(!pq.empty()){
            pair<ll,ll>top=pq.top(); 
            pq.pop();

    
            for(auto nbr:graph[top.second]){
                ll d=nbr.second;
                ll c=nbr.first;
                if(distance[c]==-1 || top.first+d <distance[c]){
                    distance[c]=top.first+d;
                    pq.push({distance[c],c});
                }
            }
        }
        return distance;
    }


    long long minimumCost(string source, string target, vector<char>& org, vector<char>& chng, vector<int>& cost) {
        ll m=org.size();
        vector<vector<pair<ll,ll>>> graph(26);
        for(ll i=0;i<m;i++){
            graph[org[i]-'a'].push_back({chng[i]-'a',cost[i]});
        }

    
        unordered_map<ll,vector<ll>>mp; // charcetr index , dist vector for this index
        ll n=source.length();
        ll res=0;

        for(ll i=0;i<26;i++){
            vector<ll>dis=bfs(i,graph);
            mp[i]=dis;
        }

        for(ll i=0;i<n;i++){
            if(source[i]!=target[i]){
                ll k=mp[source[i]-'a'][target[i]-'a'];
                if(k==-1) return -1;
                res+=k;
            }
        }
        return res;
    }
};