※ 引述 《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;
}
};