※ 引述《dont (dont)》之铭言：
: 2976. Minimum Cost to Convert String I
: ## 思路
: 先用original, changed, cost三个array建立Graph
: 扫source/target字串时对每个字符做dijkstra
: ## Complexity
: source = N
: original = M
: Time:
: Space: O(M+N)
: ## Code
: ```python
: class Solution:
: def minimumCost(self, source: str, target: str, original: List[str],
: changed: List[str], cost: List[int]) -> int:
: graph = defaultdict(list)
: for ori_ch, new_ch, c in zip(original, changed, cost):
: graph[ori_ch].append((c, new_ch))
: @cache
: def get_min_cost(src, dst):
: heap = [(0, src)]
: seen = {src: 0}
: while heap:
: curr_cost, ch = heapq.heappop(heap)
: if ch == dst:
: return curr_cost
: for next_cost, next_ch in graph[ch]:
: if next_ch not in seen or seen[next_ch] > curr_cost +
: next_cost:
: seen[next_ch] = curr_cost + next_cost
: heapq.heappush(heap, (curr_cost + next_cost, next_ch))
: return -1
: ans = 0
: for src, dst in zip(source, target):
: min_cost = get_min_cost(src, dst)
: if min_cost == -1:
: return -1
: ans += min_cost
: return ans
: ```
用Floyd-Warshall简单好多= =
不过original跟changed的配对居然有重复的 马的
```python
class Solution:
def minimumCost(self, source: str, target: str, original: List[str],
changed: List[str], cost: List[int]) -> int:
min_costs = [[float('inf')] * 26 for _ in range(26)]
for ori_ch, new_ch, c in zip(original, changed, cost):
i = ord(ori_ch) - ord('a')
j = ord(new_ch) - ord('a')
min_costs[i][j] = min(min_costs[i][j], c)
for k in range(26):
for i in range(26):
for j in range(26):
min_costs[i][j] = min(min_costs[i][j], min_costs[i][k] +
min_costs[k][j])
ans = 0
for src, dst in zip(source, target):
if src == dst:
continue
i = ord(src) - ord('a')
j = ord(dst) - ord('a')
if min_costs[i][j] == float('inf'):
return -1
ans += min_costs[i][j]
return ans
```