Gym 101196D Lost in Translation （bfs）

本文主要是介绍Gym 101196D Lost in Translation （bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

打比赛的时候没来得及看这道题目，现在补上

题目大意就是给你一篇文章，初始状态是英文，然后给出以多种语言，和一些语言之间翻译需要的成本，然后问你找出在翻译成所有语言的最低成本，但是这里还有一个条件特别重要，那就是救过必须要满足翻译成某种语言的过程必须是最短路径，理解一下，对某一种语言来说也就是求一下该语言的所有最短路径中的最低成本

思路：首先先建一下图了当然是，这种题不用看，将字符串转化为数字然后用二维数组建一下图，然后bfs就可以了，这道题有道人是规规矩矩的bfs，但是看了某大神的代码，感觉在bfs的过程中注意一些东西，就能让代码变短更加简洁，在bfs往队列里压得过程中注意要记录一下某种语言查找过的最短路径，记录成本，当然如果之前压入过队列，只需要判断一下如果现在查找的路径和原来的路径路径长度相当，那么只需更改一下最小成本就可以了，不需要再加入到队列，这样处理完只需要加所有队列里的元素对应的最低成本就是总的最低成本了，一遍bfs后直接输出即可

ac代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
int n,m;
map<string,int> mp;
int Map[105][105];
int vlue[105];
int vis[105],dep[105];
int main()
{
string s1,s2;
int x;
while(cin>>n>>m)
{
mp["Enlish"]=0;
for(int i=1;i<=n;i++)
{
cin>>s1;
mp[s1]=i;
}
memset(Map,0,sizeof(Map));
memset(dep,0,sizeof(dep));
memset(vlue,0,sizeof(vlue));
for(int i=1;i<=m;i++)
{
cin>>s1>>s2>>x;
Map[mp[s1]][mp[s2]]=x;
Map[mp[s2]][mp[s1]]=x;
}
queue<int> que;
while(!que.empty())que.pop();
que.push(0);
vis[0]=1;
vlue[0]=0;
int sum=0;
int ans=0;
while(!que.empty())
{
int u=que.front();
sum+=vlue[u];
ans++;
que.pop();
for(int i=1;i<=n;i++)
{
if(Map[u][i])
{
if(vis[i]==0)
{
vis[i]=1;
vlue[i]=Map[u][i];
dep[i]=dep[u]+1;
que.push(i);
}
else
{
if(dep[i]==dep[u]+1)
vlue[i]=min(vlue[i],Map[u][i]);
}
}
}
}
if(ans==n+1)
cout<<sum<<endl;
else
cout<<"Impossible"<<endl;
}
return 0;
}