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