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。
思路:
將original[i], changed[i], cost[i]轉換成有向圖的edge描述[from,to,cost]建構圖
從任一字母轉換到另一個字母的最少費用即是兩字母間的shortest path問題，使用
floyd washall建構all pair shortest path的矩陣後根據source、target查找最小費用
如果遇到無法轉換的字母對則回傳-1
注意的是本題的cost長度最長可到2000，代表
(original[i],changed[i])是會有重複的，所以一開始建構圖的時候graph[from][to]
的值在更新成cost[i]時需要check和原本已更新過的g[from][to]比是不是比較小，小的
話才需要更新，為了這個卡了兩個小時。
long long minimumCost(string source, string target, vector<char>& original,
vector<char>& changed, vector<int>& cost) {
//o_lac++;
vector<vector<long long int>> gr_ap(26,vector<long long int>(26,1e9));
//note row: from col: to->gr_ap[from][to]
for(int g=0;g<changed.size();++g){
int f_r=original[g]-'a';
int t_o=changed[g]-'a';
gr_ap[f_r][t_o]=min((long long)cost[g],gr_ap[f_r][t_o]);
}
for(int i=0;i<26;++i){
gr_ap[i][i]=0;
}
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
for(int h=0;h<26;h++){
if( gr_ap[j][h]>gr_ap[j][i]+gr_ap[i][h] ){
gr_ap[j][h]=gr_ap[j][i]+gr_ap[i][h];
}
}
}
}
long long int ans=0;
for(int i=0;i<source.size();++i){
if(source[i]!=target[i]){
int f_r=source[i]-'a';
int t_o=target[i]-'a';
if(gr_ap[f_r][t_o]==1e9){
ans=-1;
return ans;
}
ans+=gr_ap[f_r][t_o];
}
}
return ans;
}