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; } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.192.85 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722052462.A.948.html