昨天发懒了 对不起:(
要注意k要摆最外层，不然会错
Bellman-Ford、Floyd-Warshall、Dijkstra 是三种著名的图论算法，用于解决最短路
径问题。这些算法在使用的场合和特点上有所不同：
### 1. Bellman-Ford 算法
**特点**：
- 可以处理包含负权重边的图。
- 能够检测图中是否存在负权重循环。
- 时间复杂度为 \(O(V \times E)\)，其中 \(V\) 是顶点数，\(E\) 是边数。
**用途**：
- 适用于边数不多，且可能有负权重的图。
- 用于检测图中是否存在负权重循环。
**工作原理**：
- 对于每条边，重复更新最短路径估计值，最多 \(V-1\) 次，因为最短路径最多包含
\(V-1\) 条边。
- 第 \(V\) 次更新后，如果最短路径估计值还在变化，则存在负权重循环。
### 2. Floyd-Warshall 算法
**特点**：
- 可以解决所有顶点对之间的最短路径问题。
- 适用于稠密图，因为时间复杂度为 \(O(V^3)\)。
- 可以处理负权重边，但不能处理负权重循环。
**用途**：
- 用于计算所有顶点对之间的最短路径。
- 适用于图较小但比较稠密的情况。
**工作原理**：
- 动态规划方法：通过逐步允许经过更多的中间顶点来更新最短路径估计值。
- 最终结果为所有顶点对之间的最短路径距离。
### 3. Dijkstra 算法
**特点**：
- 适用于非负权重边的图。
- 时间复杂度为 \(O(V^2)\) 或使用优先队列优化为 \(O(E + V \log V)\)。
- 单源最短路径算法，即从单一源顶点到其他所有顶点的最短路径。
**用途**：
- 用于解决边权重非负的单源最短路径问题。
- 适用于网络路由、地图导航等问题。
**工作原理**：
- 使用优先队列选择最短路径估计值最小的顶点，并更新其邻接顶点的最短路径估计值。
- 重复此过程直到所有顶点的最短路径估计值都确定。
### 总结
- **Bellman-Ford**：适合有负权重的图，可检测负权重循环，较慢。
- **Floyd-Warshall**：适合计算所有顶点对间的最短路径，适用于较小但稠密的图。
- **Dijkstra**：适合边权重非负的图，用于单源最短路径问题，较快。
def minimumCost(self, source: str, target: str, original: List[str], changed:
List[str], cost: List[int]) -> int:
g = [[10**9 for _ in range(26)] for _ in range(26)]
for i in range(len(original)):
g[ord(original[i])-ord('a')][ord(changed[i])-ord('a')] = min(cost[i],
g[ord(original[i])-ord('a')][ord(changed[i])-ord('a')])
for i in range(26):
g[i][i] = 0
# Floyd-Warshall
for k in range(26):
for i in range(26):
for j in range(26):
if g[i][k] + g[k][j] < g[i][j]:
g[i][j] = g[i][k] + g[k][j]
ans = 0
for i in range(len(source)):
if g[ord(source[i])-ord('a')][ord(target[i])-ord('a')] == 10**9:
print(source[i], target[i])
return -1
else:
ans += g[ord(source[i])-ord('a')][ord(target[i])-ord('a')]
return ans