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