Minimum Cost to Convert String I

lcpy gen -n 2976   # by problem number
lcpy gen -s minimum_cost_to_convert_string_i   # by problem name

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert the string "abcd" to string "acbe":
- Change value at index 1 from 'b' to 'c' at a cost of 5.
- Change value at index 2 from 'c' to 'e' at a cost of 1.
- Change value at index 2 from 'e' to 'b' at a cost of 2.
- Change value at index 3 from 'd' to 'e' at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28.
It can be shown that this is the minimum possible cost.

Input: source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]
Output: 12
Explanation: To change the character 'a' to 'b' change the character 'a' to 'c' at a cost of 1, followed by changing the character 'c' to 'b' at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of 'a' to 'b', a total cost of 3 * 4 = 12 is incurred.

Input: source = "abcd", target = "abce", original = ["a"], changed = ["e"], cost = [10000]
Output: -1
Explanation: It is impossible to convert source to target because the value at index 3 cannot be changed from 'd' to 'e'.

class Solution:
    # Time: O(cost.length + 26^3 + n)
    # Space: O(26^2)
    def minimum_cost(
        self, source: str, target: str, original: list[str], changed: list[str], cost: list[int]
    ) -> int:
        unreach = 10**18
        dist = [[unreach] * 26 for _ in range(26)]
        for i in range(26):
            dist[i][i] = 0
        for o, c, w in zip(original, changed, cost, strict=True):
            dist[ord(o) - 97][ord(c) - 97] = min(dist[ord(o) - 97][ord(c) - 97], w)
        for k in range(26):
            dist_k = dist[k]
            for i in range(26):
                dist_ik = dist[i][k]
                if dist_ik == unreach:
                    continue
                dist_i = dist[i]
                for j in range(26):
                    if dist_ik + dist_k[j] < dist_i[j]:
                        dist_i[j] = dist_ik + dist_k[j]
        total = 0
        for s, t in zip(source, target, strict=True):
            d = dist[ord(s) - 97][ord(t) - 97]
            if d == unreach:
                return -1
            total += d
        return total