Leet Code Daily 2024-07-27 - Minimum Cost to Convert String

constexpr int kFarAway = 2600000;

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original,
                          vector<char>& changed, vector<int>& cost) {

        const int n = source.size(), m = original.size();

        auto distance = vector<vector<int>>(26, vector<int>(26, kFarAway));
        for (int i = 0; i < 26; i++) {
            distance[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            const int p = original[i] - 'a';
            const int q = changed[i] - 'a';
            distance[p][q] = min(distance[p][q], cost[i]);
        }
        for (int k = 0; k < 26; k++) {
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    distance[i][j] =
                        min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }
        }

        long long ret = 0;
        for (int i = 0; i < n; i++) {
            const int p = source[i] - 'a';
            const int q = target[i] - 'a';
            if (distance[p][q] >= kFarAway) {
                return -1;
            }
            ret += distance[p][q];
        }
        return ret;
    }
};