【刷图】最短路径算法
最短路径算法
Floyd算法
a) 初始化:D[u,v]=A[u,v]
b) For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
c) 算法结束:D即为所有点对的最短路径矩阵
2976. 转换字符串的最小成本 I
给你两个下标从 0 开始的字符串 source 和 target ,它们的长度均为 n 并且由 小写 英文字母组成。
另给你两个下标从 0 开始的字符数组 original 和 changed ,以及一个整数数组 cost ,其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。
你从字符串 source 开始。在一次操作中,如果 存在 任意 下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。
返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换,则返回 -1 。
注意,可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。
示例 1:
输入:source = “abcd”, target = “acbe”, original = [“a”,“b”,“c”,“c”,“e”,“d”], changed = [“b”,“c”,“b”,“e”,“b”,“e”], cost = [2,5,5,1,2,20]
输出:28
解释:将字符串 “abcd” 转换为字符串 “acbe” :
- 更改下标 1 处的值 ‘b’ 为 ‘c’ ,成本为 5 。
- 更改下标 2 处的值 ‘c’ 为 ‘e’ ,成本为 1 。
- 更改下标 2 处的值 ‘e’ 为 ‘b’ ,成本为 2 。
- 更改下标 3 处的值 ‘d’ 为 ‘e’ ,成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。
可以证明这是可能的最小成本。
示例 2:
输入:source = “aaaa”, target = “bbbb”, original = [“a”,“c”], changed = [“c”,“b”], cost = [1,2]
输出:12
解释:要将字符 ‘a’ 更改为 ‘b’:
- 将字符 ‘a’ 更改为 ‘c’,成本为 1
- 将字符 ‘c’ 更改为 ‘b’,成本为 2
产生的总成本是 1 + 2 = 3。
将所有 ‘a’ 更改为 ‘b’,产生的总成本是 3 * 4 = 12 。
示例 3:
输入:source = “abcd”, target = “abce”, original = [“a”], changed = [“e”], cost = [10000]
输出:-1
解释:无法将 source 字符串转换为 target 字符串,因为下标 3 处的值无法从 ‘d’ 更改为 ‘e’ 。
class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
int dis[26][26];
memset(dis, 0x3f, sizeof(dis));
for (int i = 0; i < 26; i++) {
dis[i][i] = 0;
}
for (int i = 0; i < cost.size(); i++) {
int x = original[i]-'a';
int y = changed[i]-'a';
dis[x][y] = min(dis[x][y], cost[i]);
}
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}
}
}
long long ans = 0;
for (int i = 0; i < source.length(); i++) {
int d = dis[source[i]-'a'][target[i]-'a'];
if (d == 0x3f3f3f3f) {
return -1;
}
ans += d;
}
return ans;
}
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!