33B - String Problem - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
 
const int maxn = 1e6 + 10;
const int MOD = 1e9+7;
 
ll	ans[30][30], dist[30];
bool mark[30];
vector<pair<int, int>> vec[30];

void dijkstra(int st){
	set<pair<int, int>> s;
	for(int i = 0; i < 27; i++){
		dist[i] = (i == st? 0: 1000000000);
		mark[i] = (i == st? 1: 0);
		s.insert({dist[i], i});
	}
	
	while(s.size()){
		pii cur = *s.begin();
		s.erase(cur);
		int v = cur.S;
		for(auto i : vec[v]){
			ll u = i.F, w = i.S;
			mark[u] = 1;
			if(dist[u] > dist[v] + w){
				s.erase({dist[u], u});
				s.insert({dist[u] = dist[v] + w, u});
			}
		}
	}
	
	for(int i = 0; i < 27; i++){
		if(mark[i])	ans[st][i] = dist[i];
		else ans[st][i] = -1;
	}
}

void solve(){
	string s, s1;
	int n;
	cin>> s>> s1>> n;
	
	if(s.size() != s1.size()){
		cout<< -1;
		return;
	}
	
	for(int i = 0; i < n; i++){
		char x, y; int w;
		cin>> x>> y>> w;

		vec[x - 'a'].pb({y - 'a', w});
	}
	
	for(int i = 0; i < 27; i++)	dijkstra(i);
	
	vector <int> vec;
	int anss = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i] == s1[i]){
			vec.pb(s[i] - 'a');
			continue;
		}
		int idk = -1;
		int idk1 = 100000000;
		for(int j = 0; j < 27; j++){
			if(ans[s[i] - 'a'][j] == -1 || ans[s1[i] - 'a'][j] == -1){
				continue;
			}
			if(idk1 > ans[s[i] - 'a'][j] + ans[s1[i] - 'a'][j]){
				idk = j;
				//cout<< (ans[s[i] - 'a'][j] + ans[s1[i] - 'a'][j] )<< " " << j << endl;
				idk1 = ans[s[i] - 'a'][j] + ans[s1[i] - 'a'][j];
			}
		}
		if(idk == -1){
			cout<< -1;
			return;
		}
		vec.pb(idk);
		anss += idk1;
	}
	cout<< anss << endl;;
	for(int i = 0; i < vec.size(); i++){
		cout<< ((char)(vec[i] + 'a')) ;
	}

}
	
int main(){
	fast_io
	solve();
	return 0;	
}