→ DJYOMIYAHINA: 大師 07/27 14:15
推 enmeitiryous: 用dijkstra 會卡重複edge 的問題嗎？ 07/27 15:07
→ dont: 不會欸 因為graph是存array 不會把重複的覆蓋掉 07/27 18:07
※ 引述《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
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.59 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722060581.A.585.html