1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <cstring>
#include <vector>

const int INF = 0x3fff'ffff;

class Solution {
public:
    long long minimumCost(std::string source, std::string target, std::vector<char>& original, std::vector<char>& changed, std::vector<int>& cost) {
        std::vector<std::vector<int>> dist(26, std::vector<int>(26, INF));
        for (int i = 0; i < original.size(); ++i) {
            dist[original[i] - 'a'][changed[i] - 'a'] = std::min(dist[original[i] - 'a'][changed[i] - 'a'], cost[i]);
        }
        
        for (int k = 0; k < 26; ++k) {
            for (int i = 0; i < 26; ++i) {
                for (int j = 0; j < 26; ++j) {
                    if (i != j && dist[i][k] < INF && dist[k][j] < INF) {
                        dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        long long int res = 0;
        for (int i = 0; i < source.length(); ++i) {
            if (source[i] == target[i]) {
                continue;
            }
            int cost = dist[source[i] - 'a'][target[i] - 'a'];
            if (cost < INF) {
                res += cost;
            }
            else {
                return -1;
            }
        }
        return res;
    }
};