fork(4) download
copy 
  1. #include<cstdio>
  2. #include<string>
  3. #include<queue>
  4. #include<vector>
  5. #include<iostream>
  6. #include<map>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     int i,j,k,m,n,t,tcase=1,p;
  12.     string a,b;
  13.     scanf("%d",&t);
  14.     while(t--){
  15.         printf("\n");
  16.         vector<int>list[2000];
  17.         map<char,int>maps1;
  18.         map<int,char>maps2;
  19.         scanf("%d %d",&m,&n);
  20.         for(i=1,j=1;i<=m;i++){
  21.             cin>>a>>b;
  22.             if(maps1[a[0]]==0) maps1[a[0]]=j,maps2[j]=a[0],j++;
  23.             if(maps1[b[0]]==0) maps1[b[0]]=j,maps2[j]=b[0],j++;
  24.             list[maps1[a[0]]].push_back(maps1[b[0]]);
  25.             list[maps1[b[0]]].push_back(maps1[a[0]]);
  26.         }
  27.         for(p=1;p<=n;p++){
  28.             int flag=0;
  29.             cin>>a>>b;
  30.             vector<int>taken(2000);
  31.             vector<string>level(2000);
  32.             queue<int>q;
  33.             q.push(maps1[a[0]]);
  34.             taken[maps1[a[0]]]=1;
  35.             level[maps1[a[0]]]=a[0];
  36.             while(!q.empty()){
  37.                 k=q.front();
  38.                 for(i=0;i<list[k].size();i++){
  39.                     if(taken[list[k][i]]==0){
  40.                         taken[list[k][i]]=1;
  41.                         level[list[k][i]]=level[k]+maps2[list[k][i]];
  42.                         q.push(list[k][i]);
  43.                         if(maps2[list[k][i]]==b[0]){
  44.                             cout<<level[list[k][i]]<<"\n";
  45.                             flag=1;
  46.                             break;
  47.                         }
  48.                     }
  49.                 }
  50.                 if(flag==1) break;
  51.                 q.pop();
  52.             }
  53.         }
  54.     }
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0s 3308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/y8wRUO
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!