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;
}