本文涉及知识点

C++图论 最短路 分治法

LeetCode2976. 转换字符串的最小成本 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’ 。

提示：
1 <= source.length == target.length <= 10⁵
source、target 均由小写英文字母组成
1 <= cost.length== original.length == changed.length <= 2000
original[i]、changed[i] 是小写英文字母
1 <= cost[i] <= 10⁶
original[i] != changed[i]

分治法+多源最短路

任意s[i]的转换都是独立的，相互无影响。一次转换看成一条有向边，多次转换就是最短路。
注意：
相同字符无需转换。
任意字符无法转换，返回-1。
时间复杂度：O($\sum$³ + n)。
$\sum$ = 26，时间复杂度：O($\sum$³)

代码

核心代码

template<class T = int >
class CFloyd
{
public:
	CFloyd(int n, const T INF = 1000 * 1000 * 1000):m_INF(INF)
	{
		m_vMat.assign(n, vector<T>(n, m_INF));
		for (int i = 0; i < n; i++) {
			m_vMat[i][i] = 0;
		}
	}
	void SetEdge(int i1, int i2,const T& dis, bool bDirect = false)
	{
		m_vMat[i1][i2] = min(m_vMat[i1][i2],dis);
		if (!bDirect) {
			m_vMat[i2][i1] = m_vMat[i1][i2];
		}
	}
	vector<vector<T>> Dis()
	{
		auto vResMat = m_vMat;
		const int n = m_vMat.size();
		for (int i = 0; i < n; i++)
		{//通过i中转
			for (int i1 = 0; i1 < n; i1++)
			{
				if (m_INF == vResMat[i1][i])
				{
					continue;
				}
				for (int i2 = 0; i2 < n; i2++)
				{
					//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
					vResMat[i1][i2] = min(vResMat[i1][i2], vResMat[i1][i] + vResMat[i][i2]);
					//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
				}
			}
		}
		return vResMat;
	};
	vector<vector<T>> m_vMat;//结果串
	const T m_INF;
};

class Solution {
		public:
			long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
				CFloyd floyd(26);
				for (int i = 0; i < original.size(); i++) {
					floyd.SetEdge(original[i] - 'a', changed[i] - 'a', cost[i],true);
				}
				auto dis = floyd.Dis();
				long long ans = 0;
				for (int i = 0; i < source.length(); i++) {
					if (source[i] == target[i])continue;
					const int iDis = dis[source[i] - 'a'][target[i] - 'a'];
					if (floyd.m_INF == iDis)return -1;
					ans += iDis;
				}
				return ans;
			}
		};

单元测试

string source, target;
		vector<char> original, changed;
		vector<int> cost;
		TEST_METHOD(TestMethod11)
		{
			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 };
			auto res = Solution().minimumCost(source, target, original, changed, cost);
			AssertEx(28LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			source = "aaaa", target = "bbbb", original = { 'a','c' }, changed = { 'c','b' }, cost = { 1,2 };
			auto res = Solution().minimumCost(source, target, original, changed, cost);
			AssertEx(12LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			source = "abcd", target ="abce", original = { 'a' }, changed = { 'e' }, cost = { 10000 };
			auto res = Solution().minimumCost(source, target, original, changed, cost);
			AssertEx(-1LL, res);
		}