※ 引述《oin1104 (是oin的說)》之銘言：
: ※ 引述 《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;
: }
: };
思路:
Floyd-Warshall
查了一下 先做成i為起點j為終點的圖 之後再加入中間點k計算
這樣就能找出最短距離
新的方法+1
還不錯
等等寫昨天的
然後這個有重複的 超哭
然後寫得滿醜的
Python Code:
class Solution:
def minimumCost(self, source: str, target: str, original: List[str],
changed: List[str], cost: List[int]) -> int:
graph = [[float("inf") if i != j else 0 for j in range(26)] for i in
range(26)]
for i in range(len(original)):
graph[ord(original[i])-ord("a")][ord(changed[i])-ord("a")] =
min(graph[ord(original[i])-ord("a")][ord(changed[i])-ord("a")], cost[i])
for k in range(26):
for i in range(26):
for j in range(26):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
result = 0
for i in range(len(source)):
if graph[ord(source[i])-ord("a")][ord(target[i])-ord("a")] ==
float("inf"):
return -1
result += graph[ord(source[i])-ord("a")][ord(target[i])-ord("a")]
return result