欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

相关标签: 最短路 思维