CF33B String Problem 题解

题目链接：CF33B String Problem

题意：

萌妹纸 cxy 喜欢字符串和妹纸。而且她更喜欢它们相同。这就是为什么在闲暇时间里，cxy 会玩以下游戏。她拿任意两个由小写拉丁字母组成的字符串，并试图使它们相同。根据游戏规则，每次移动，cxy可以将字符串中的任意字符$A_i$改变为任意字符$B_i$，但她必须为每次移动付出一定的金钱，金额等于$W_i$。她可以根据需要进行任意次移动。由于cxy是个非常节俭的妹纸，从不浪费她的钱，她请教你这位经验丰富的程序员，帮她回答这个问题：cxy应该拥有多少最少的金钱才能得到相同的字符串。

输入格式：

第一行输入包含两个初始非空字符串$s$和$t$，由小写拉丁字母组成。每个字符串的长度不超过$10^5$。接下来的一行包含整数$n(0 \leq n \leq 500)$，表示可能的更改次数。然后是$n$行，每行包含字符$A_i$和$B_i$（小写拉丁字母）以及整数$W_i\left(0 \leq W_i \leq 100\right)$，表示可以在任何一个字符串中将字符$A_i$更改为字符$B_i$并花费金额$W_i$。

输出格式：

如果存在答案，则输出问题的答案和结果字符串。否则，在一行中输出 $-1$。如果答案不唯一，可以输出任何一个答案。

容易发现这题的坑在于最后的 $s$ 可能有 $a,b$ 中没出现的字母。其实就是提示一下你需要枚举要变成哪个字母。

我们枚举要变换的字母 $c$ ，然后计算 $W(a\leadsto c) + W(b\leadsto c)$ ，这个 $W$ 可以用 Floyd 算出来。

时间复杂度 $\mathcal{O}(26L)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x7f7f7f7f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

char u,v,a[N],b[N],s[N]; int n,res,g[35][35];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (a + 1) >> (b + 1) >> n; memset(g, 0x3f, sizeof(g));
    if(strlen(a + 1) != strlen(b + 1)) return cout << "-1" << '\n', 0;
    for(int i = 1; i <= 26; i++) g[i][i] = 0;
    for(int i = 1, w; i <= n; i++)
    {
        cin >> u >> v >> w; u -= 'a' - 1; v -= 'a' - 1;
        if(g[u][v] > w) { g[u][v] = w; }
    }
    for(int k = 1; k <= 26; k++)
        for(int i = 1; i <= 26; i++)
            for(int j = 1; j <= 26; j++)
                down(g[i][j], g[i][k] + g[k][j]);
    
    for(int i = 1, mn = INF; a[i]; i++, mn = INF)
    {
        if(a[i] == b[i]) { s[i] = a[i]; continue; }
        for(int c = 1; c <= 26; c++)
        {
            int cost = g[a[i] - 'a' + 1][c] + g[b[i] - 'a' + 1][c];
            if(cost < mn) { mn = cost, s[i] = (c + 'a' - 1); }
        }
        if(mn == INF) return cout << "-1" << '\n', 0; else res += mn;
    }
    cout << res << '\n' << (s + 1) << '\n';
    return 0;
}