登录
dijstra 模板题（对每个字母运行一次dijstra算法）
2024年2月27日 20:59
Problem: 2976. 转换字符串的最小成本 I
[TOC]
思路
dijstra 模板题（对每个字母运行一次dijstra算法）
Code
###Python3
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
# 先建图,有向图（26个字母映射到0-25）
g = [[] for _ in range(26)]
dt = defaultdict()
n = len(original)
for i, x in enumerate(original):
y = changed[i]
c = cost[i]
x0 = ord(x) - ord('a')
y0 = ord(y) - ord('a')
if (x0, y0) not in dt.keys():
dt[(x0, y0)] = c
g[x0].append(y0)
else:
dt[(x0, y0)] = min(c, dt[(x0, y0)])
# 运行dijstra 算法，统计所有点（26个字母）能到达的其他点的最短距离
final_dt = defaultdict()
# dijstra算法 统计x能到达的所有点点最短距路
def dfs (x: int) -> None:
dist = {} # 本次dijstra统计的距离，后续加到final_dt中
unvisited_nodes = {} # 先用广度优先搜索将x能达到的点初始化到inf
q = [(0, x, x)]
vis = [0] * 26
cur = [x]
vis[x] = 1
while cur:
pre = cur
cur = []
for el in pre:
for y in g[el]:
if vis[y] == 0:
unvisited_nodes[(x, y)] = inf
vis[y] = 1
cur.append(y)
# 开始最小路径搜索
unvisited_nodes[(x, x)] = 0
seen = set()
# 使用 dijstra算法计算达到各店的最短值
while unvisited_nodes:
current_distance, x1, y1 = heapq.heappop(q)
if y1 in seen:
continue
seen.add(y1)
for el in g[y1]:
if (x, el) not in unvisited_nodes: continue
new_distance = current_distance + dt[(y1,el)]
if new_distance < unvisited_nodes[(x, el)]:
unvisited_nodes[(x, el)] = new_distance
heapq.heappush(q, (new_distance, x, el))
dist[(x,y1)] = current_distance
unvisited_nodes.pop((x, y1))
for k, v in dist.items():
final_dt[k] = v
# 对每个字母运行dijstra算法
for i in range(26):
dfs(i)
ans = 0
# 统计完，开始对每个字母改变计算答案，如果达不到，返回-1
for i, x in enumerate(source):
x1 = ord(x) - ord('a')
y1 = ord(target[i]) - ord('a')
if x1 != y1:
if (x1, y1) not in final_dt.keys():
return - 1
else:
ans += final_dt[(x1, y1)]
return ans
