当前位置:首页 > 数据结构 > 2018 蓝桥杯省赛 B 组模拟赛(一) 封印之门-计蒜客

2018 蓝桥杯省赛 B 组模拟赛(一) 封印之门-计蒜客

https://nanti.jisuanke.com/t/20692

蒜头君被暗黑军团包围在一座岛上,所有通往近卫军团的路都有暗黑军团把手。幸运的是,小岛上有一扇上古之神打造的封印之门,可以通往近卫军团,传闻至今没有人能解除封印。

封印之门上有一串文字,只包含小写字母,有 k种操作规则,每个规则可以把一个字符变换成另外一个字符。经过任意多次操作以后,最后如果能把封印之门上的文字变换成解开封印之门的文字,封印之门将会开启。

蒜头君战斗力超强,但是不擅计算,请你帮忙蒜头君计算至少需要操作多少次才能解开封印之门。

输入格式

输入第一行一个字符串,长度不大于 1000,只包含小写字母,表示封印之门上的文字。

输入第二行一个字符串,只包含小写字母,保证长度和第一个字符串相等,表示能解开封印之门的文字。

输入第三行一个整数 k(0 \le k \le 676)

接下来 k 行,每行输出两个空格隔开的字符 ab,表示一次操作能把字符 a 变换成字符 b

输出格式

如果蒜头君能开启封印之门,输出最少的操作次数。否则输出一行 -1

样例输入

abcd
dddd
3
a b
b c
c d

样例输出

6

求出两点间的最短路

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

vector<int>vec[30];
int val[30][30],vis[30];

struct p{
    int u,dis;
    bool operator <(const p &r) const{
        return  dis>r.dis;
    }
};

void dijkstra(int s){
    priority_queue<p>q;
    memset(vis,0,sizeof(vis));

    q.push((p){s,0});
    val[s][s]=0;
    while(!q.empty()){
        p now=q.top();
        q.pop();
        if(vis[now.u]) continue;
        vis[now.u]=1;
        for(int i=0;i<vec[now.u].size();i++){
            int k=vec[now.u][i];
            if(val[s][k]==0x3f3f3f3f){
                val[s][k]=now.dis+1;
            }else{
                val[s][k]=min(now.dis+1,val[s][k]);
            }
            q.push((p){k,now.dis+1});
        }
    }
}

int main(){
    char str[1005],target[1005],a,b;
    memset(val,0x3f,sizeof(val));
    scanf("%s %s",str,target);
    int k;
    scanf("%d%*c",&k);
    while(k--){
        scanf("%c %c%*c",&a,&b);
        vec[a-'a'].push_back(b-'a');
    }
    for(int i=0;i<='z'-'a';i++){
        dijkstra(i);
    }

    int ans=0;
    for(int i=0;str[i];i++){
        if(val[str[i]-'a'][target[i]-'a']==0x3f3f3f3f){
            printf("-1\n");
            return 0;
        }else{
            ans+=val[str[i]-'a'][target[i]-'a'];
        }
    }
    printf("%d\n",ans);
    return 0;
}
/*
aaaaa
bbbbb
5
a c
c d
d b
a e
e b
10
*/


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=463

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。