做球球棒棒糖网站源码,河南省住房和城乡建设门户网站,小说网站开发的实际意义,网站建设合同 简单题目#xff1a;
蒜头君被暗黑军团包围在一座岛上#xff0c;所有通往近卫军团的路都有暗黑军团把手。幸运的是#xff0c;小岛上有一扇上古之神打造的封印之门#xff0c;可以通往近卫军团#xff0c;传闻至今没有人能解除封印。
封印之门上有一串文字#xff0c;只包…题目
蒜头君被暗黑军团包围在一座岛上所有通往近卫军团的路都有暗黑军团把手。幸运的是小岛上有一扇上古之神打造的封印之门可以通往近卫军团传闻至今没有人能解除封印。
封印之门上有一串文字只包含小写字母有 k 种操作规则每个规则可以把一个字符变换成另外一个字符。经过任意多次操作以后最后如果能把封印之门上的文字变换成解开封印之门的文字封印之门将会开启。
蒜头君战斗力超强但是不擅计算请你帮忙蒜头君计算至少需要操作多少次才能解开封印之门。
输入格式
输入第一行一个字符串长度不大于 1000只包含小写字母表示封印之门上的文字。
输入第二行一个字符串只包含小写字母保证长度和第一个字符串相等表示能解开封印之门的文字。
输入第三行一个整数 k(0≤k≤676)。
接下来 k 行每行输出两个空格隔开的字符 a, b表示一次操作能把字符 a 变换成字符 b。
输出格式
如果蒜头君能开启封印之门输出最少的操作次数。否则输出一行−1。
样例输入
abcd dddd 3 a b b c c d
样例输出
6
分析
这仅仅只是涉及最短路径的算法是个水题但是我写完老是过不去原因是我用的Floyd算法写的有问题三个for循环第一层for循环必须是中间变量放在别的位置则就改变了这个算法的思想导致错误记录一下吧害
AC代码
#includebits/stdc.h
using namespace std;
const int inf0x3f3f3f3f3f;
string u,v;
int t;
int book[110][110];
int main(){cinuv;cint;int sum0,flag0;memset(book,inf,sizeof(book));for(int i0;i26;i) book[i][i]0;for(int i0;it;i){char a,b;cinab;if(a!b)book[a-a][b-a]1;}for(int k0;k26;k)for(int i0;i26;i)for(int j0;j26;j)book[i][j]min(book[i][j],book[i][k]book[k][j]);for(int i0;iu.size();i){if(book[u[i]-a][v[i]-a]inf){flag1;break;}else sumbook[u[i]-a][v[i]-a];}flag1?cout-1endl:coutsumendl;return 0;
}
