[演算法心得] Codeforces. String Problem

jimmyhealer

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 c/c++ 版，如果大家很熱絡的話再申請 演算法/競賽程式 版吧!

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: String Problem
題目網站: Codefoces
題目網址: https://codeforces.com/problemset/problem/33/B
題目內容:

Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change one arbitrary character Ai in one of the strings into arbitrary character Bi, but he has to pay for every move a particular sum of money, equal to Wi. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings.

題目大意:

給你兩個字串，和一些轉換字元的規則及費用。
問你花最小的錢，讓兩個字串相等。

範例輸入 #1:
uayd
uxxd
3
a x 8
x y 13
d c 3

範例輸出 #1:
21
uxyd

範例輸入 #2:
a
b
3
a b 2
a b 3
b a 5

範例輸出 #2:
2b
--------------------------------------------------- 題解心得 ---------------------------------------------------

第一眼看到要最小花費，又有轉換以為是 DP，後來仔細想想字串前後沒有關係，所以直接單獨看一個字元的最小轉換花費。
接著可以思考如何找出最小花費，仔細研究轉換規則後可以轉成有向圖，有向圖就可以找最短路徑。

例如:
a → b → e  (10)
c → e         (20)
如上面這種情況，a 跟 c 要轉換成同一個字元 可以轉換成 e ，而花費會是 30。

AC code (30ms, 1.6 MB)

1. #include<bits/stdc++.h>
   
2. #define ll long long
   
3. #define INF 0x3f3f3f3f
   
4. #define MOD 1000000007
   
5. #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   
6. using namespace std;
   
7. const int MXN = 30;
   
8. 
   
9. int path[MXN][MXN];
   
10. int dis[MXN];
    
11. 
    
12. void dijkstra(int s){
    
13.   memset(dis, INF, sizeof(dis));
    
14.   dis[s] = 0;
    
15.   priority_queue<pair<int, int>, vector<pair<int, int> > , greater<pair<int, int> > > pq;
    
16.   pq.push({dis[s], s});
    
17.   while(!pq.empty()){
    
18.     auto [w, u] = pq.top(); pq.pop();
    
19.     for(int v = 0; v < 26; ++v){
    
20.       if(dis[v] > dis[u] + path[u][v]){
    
21.         dis[v] = dis[u] + path[u][v];
    
22.         pq.push({dis[v], v});
    
23.       }
    
24.     }
    
25.   }
    
26. }
    
27. 
    
28. void sol(){
    
29.   ll ans = 0, n = 0, m = 0, k = 0;
    
30.   string s1, s2;
    
31.   cin >> s1 >> s2;
    
32.   cin >> n;
    
33.   memset(path, INF, sizeof(path));
    
34.   for(int i = 0; i < n; ++i){
    
35.     char u, v;
    
36.     int w;
    
37.     cin >> u >> v >> w;
    
38.     if(w < path[u - 'a'][v - 'a'])
    
39.       path[u - 'a'][v - 'a'] = w;
    
40.   }
    
41.   for(int i = 0; i < 26; ++i){
    
42.     dijkstra(i);
    
43.     for(int j = 0; j < 26; ++j){
    
44.       path[i][j] = dis[j];
    
45.     }
    
46.   }
    
47. 
    
48.   if(s1.size() != s2.size()){
    
49.     cout << "-1";
    
50.     return;
    
51.   }
    
52. 
    
53.   for(int i = 0; i < (int)s1.size(); ++i){
    
54.     int tmp = INF;
    
55.     char tmpc = s1[i];
    
56.     for(int j = 0; j < 26; ++j){
    
57.       if(tmp > path[s1[i] - 'a'][j] + path[s2[i] - 'a'][j]){
    
58.         tmp = path[s1[i] - 'a'][j] + path[s2[i] - 'a'][j];
    
59.         tmpc = j + 'a';
    
60.       }
    
61.     }
    
62.     s1[i] = tmpc;
    
63.     ans += tmp;
    
64.   }
    
65.   if(ans > INF){
    
66.     cout << "-1\n";
    
67.     return;
    
68.   }
    
69.   cout << ans << '\n';
    
70.   cout << s1 << '\n';
    
71. }
    
72. 
    
73. int main(){
    
74.   io
    
75.   int t = 1;
    
76.   while(t--){
    
77.     sol();
    
78.   }
    
79. }
    
80. 
    

複製代碼