电子商务网站建设与管理基础,让你做一个旅游网站你会怎么做,虚拟主机如何做网站,ai制作海报蒜头君被暗黑军团包围在一座岛上#xff0c;所有通往近卫军团的路都有暗黑军团把手。幸运的是#xff0c;小岛上有一扇上古之神打造的封印之门#xff0c;可以通往近卫军团#xff0c;传闻至今没有人能解除封印。封印之门上有一串文字#xff0c;只包含小写字母#xff0…蒜头君被暗黑军团包围在一座岛上所有通往近卫军团的路都有暗黑军团把手。幸运的是小岛上有一扇上古之神打造的封印之门可以通往近卫军团传闻至今没有人能解除封印。封印之门上有一串文字只包含小写字母有 kk种操作规则每个规则可以把一个字符变换成另外一个字符。经过任意多次操作以后最后如果能把封印之门上的文字变换成解开封印之门的文字封印之门将会开启。蒜头君战斗力超强但是不擅计算请你帮忙蒜头君计算至少需要操作多少次才能解开封印之门。输入格式输入第一行一个字符串长度不大于 10001000只包含小写字母表示封印之门上的文字。输入第二行一个字符串只包含小写字母保证长度和第一个字符串相等表示能解开封印之门的文字。输入第三行一个整数 k(0 \le k \le 676)k(0≤k≤676)。接下来 kk 行每行输出两个空格隔开的字符 aa, bb表示一次操作能把字符 aa 变换成字符 bb。输出格式如果蒜头君能开启封印之门输出最少的操作次数。否则输出一行 -1−1。样例输入abcd
dddd
3
a b
b c
c d样例输出
6题意就是给出我们从一个字符串走到另一个字符串的目标 然后给出某几个字符的单项路线
求每个字符转化的最短路径之和是多少分析
可以用floyd求传递闭包的方法 对于图中给出的路径a-b 那么就表示e[a][b]1 用flody跑最短路
复杂度也不高O26*26*26
注意输入数据中路径的两个点可能会相同
#includebits/stdc.h
using namespace std;
const int maxd 1e7;
int e[30][30];int main()
{ios::sync_with_stdio(0);string from,to;getline(cin,from);getline(cin,to);int k;cink;while(k--){char ss,ee;cinssee;if(ssee)continue;e[ss-a][ee-a]1;} for(int i0;i26;i){for(int j0;j26;j)if(i!je[i][j]0)e[i][j] maxd;}for(int k0;k26;k){for(int i0;i26;i){for(int j0;j26;j)if(e[i][j]e[i][k]e[k][j])e[i][j] e[i][k]e[k][j];}}int ans0;for(int i0;ifrom.length();i){char a from[i];char b to[i];if(e[a-a][b-a]!maxd)anse[a-a][b-a];else {ans-1;break;}}coutansendl;return 0;
}
