cf 33B string problem
程序员文章站
2022-06-15 09:38:13
题目这题其实不难,以前也做过类似的。我们先用floyd传递闭包,求出任意两个字母的最短路径。轮到字符串变换的时候,注意要枚举26个字母,不一定把a[i] 换成b[i]是最优的,有可能换成其他的更优,注意这点和其他细节就好了。#include#include#include#include#includeusing namespace std;...
这题其实不难,以前也做过类似的。我们先用floyd传递闭包,求出任意两个字母的最短路径。轮到字符串变换的时候,注意要枚举26个字母,不一定把a[i] 换成b[i]是最优的,有可能换成其他的更优,注意这点和其他细节就好了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
using namespace std;
int g[30][30],n,len1,len2,ans;
char s1[100005],s2[100005],c1,c2;
string s;
int main()
{
ios::sync_with_stdio(false);
cin>>s1+1>>s2+1;
len1=strlen(s1+1);
len2=strlen(s2+1);
for(int i=1;i<=29;i++)
{
for(int j=1;j<=29;j++)
{
g[i][j]=1e8;
if(i==j)g[i][j]=0;
}
}
cin>>n;
for(int i=1;i<=n;i++)
{
int zhi;
cin>>c1>>c2>>zhi;
g[c1-'a'+1][c2-'a'+1]=min(g[c1-'a'+1][c2-'a'+1],zhi);
}
if(len1!=len2)
{
cout<<"-1";
return 0;
}
for(int k=1;k<=26;k++)
{
for(int i=1;i<=26;i++)
{
for(int j=1;j<=26;j++)
{
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
for(int i=1;i<=len1;i++)
{
if(s1[i]==s2[i])
{
s+=s1[i];
}
else
{
int zhong=1e8,wei;
for(int j=1;j<=26;j++)
{
if(g[s1[i]-'a'+1][j]+g[s2[i]-'a'+1][j]<zhong)
{
zhong=g[s1[i]-'a'+1][j]+g[s2[i]-'a'+1][j];
wei=j;
}
}
if(zhong==1e8)
{
printf("-1");return 0;
}
else
{
s+=wei+'a'-1;
ans+=zhong;
}
}
}
cout<<ans<<endl<<s;
}
本文地址:https://blog.csdn.net/qq_37073764/article/details/107368691
推荐阅读
-
CF1204D Kirk and a Binary String
-
cf1121F. Compress String(后缀自动机)
-
(string高精度)A + B Problem II hdu1002
-
牛客多校第三场 A-Clam and Fish【贪心】+ B-Classical String Problem【思维】
-
cf914F. Substrings in a String(bitset 字符串匹配)
-
cf868F. Yet Another Minimization Problem(决策单调性 分治dp)
-
CF1204D Kirk and a Binary String
-
cf 33B string problem
-
石油大--Contest2022 - 2020年秋季组队训练赛第二场--17100 Problem D、Find String in a Grid (AC自动机)
-
Mediocre String Problem Gym - 101981M (拓展KMP + PAM回文自动机)