做了道力扣题，基本就是板子类型。虽然Floyd-Warshall算法的实现不难，比Dijkstra简单多了，但是还是有不少细节需要注意。

2976. 转换字符串的最小成本 I

思路

这题简单归约一下，就可以看出要用Floyd-Warshall算法。每个字母视作一个节点， original 、 changed 和 cost 给出了对应边的权重。我们开个 G[26][26] 的二维数组就可以解决问题，先进行预处理

int G[26][26];
for (int i = 0; i < 26; i++) {
    for (int j = 0; j < 26; j++) {
        G[i][j] = INT_MAX;
        if (i == j) G[i][j] = 0;
    }
}
for (int i = 0; i < original.size(); i++) {
    G[original[i] - 'a'][changed[i] - 'a'] = min(G[original[i] - 'a'][changed[i] - 'a'], cost[i]); // 注意取最小值
}

值得一提的是在读取边的信息的时候，可能会有多条边连接同一对节点，我们要取最小值，以及在初始化的时候要把所有 G[i][i] 设为0。

接下来就是Floyd-Warshall的三重循环了：

for (int k = 0; k < 26; k++) {
    for (int i = 0; i < 26; i++) {
        if (G[i][k] == INT_MAX) continue;
        for (int j = 0; j < 26; j++) {
            if (G[k][j] != INT_MAX && G[i][k] + G[k][j] < G[i][j]) {
                G[i][j] = G[i][k] + G[k][j];
            }
        }
    }
}

k 是中转节点，必须放在最外层循环。更新的时候我们可以进行“剪枝”，如果 G[i][k] 是无穷大，说明 i 到 k 不可达，没必要继续往下，可以直接跳过整个循环。在最内层循环中，我们同样要检查 G[k][j] 是否为无穷大，避免溢出。

最后计算出答案即可，记得开 long long 。

long long ans = 0;
for (int i = 0; i < source.size(); i++) {
    int len = G[source[i] - 'a'][target[i] - 'a'];
    if (len == INT_MAX) return -1;
    else ans += len;
}
return ans;