※ 引述 《enmeitiryous (enmeitiryous)》 之铭言：
:
: 2976. minium cost to convert string 1
: 题目:给你两个string source, target，目标是要将source convert to target
: 并给你两个array: original, changed其中original[i],changed[i]配对代表你
: 可以将char: original[i]变换成changed[i]并花费另一个array: cost[i]的花费
: ，回传将source转换成target所需的最小花费，如果无法转换则回传-1。
:
:
思路:
原本想说是不是用dp写的
可是想了想
dp的话
必须搭配dfs或是其他东西
才能在那些里找到对的变化方式
所以想了想
发现字母只有26个
所以建图然后直接套著用比较快
建图的方式
是对每个字做Dijkstra's
然后姆咪姆咪就好ㄌ
干你娘:
我刚刚解完
觉得我无敌了 跟鬼一样
就去看这题的第二题
就是hard难度的
这题好像就要用dp加上图了
看了看
不会
果断放弃
吃晚餐喽
class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original,
vector<char>& changed, vector<int>& cost)
{
int len = original.size();
unordered_map<char, vector<pair<char,int>> > save;
vector<vector<int>> paper(26,vector<int>(26,INT_MAX));
for(int i = 0 ; i < len ; i ++)
{
save[original[i]].push_back({changed[i],cost[i]});
}
queue<char> find;
for(int i = 0 ; i < 26 ; i ++)
{
paper[i][i] = 0;
find.push(i+'a');
while(!find.empty())
{
char nowfind = find.front();
for(auto k : save[nowfind])
{
int jiwp = paper[i][nowfind-'a'] + k.second;
if(jiwp < paper[i][k.first-'a'])
{
paper[i][k.first-'a'] = jiwp;
find.push(k.first);
}
}
find.pop();
}
}
long long res = 0;
int slen = source.size();
for(int i = 0 ; i < slen ; i ++)
{
if(paper[source[i]-'a'][target[i]-'a'] == INT_MAX)return -1;
res += paper[source[i]-'a'][target[i]-'a'];
}
return res;
}
};