Code: Select all
#include <bits/stdc++.h>
using namespace std;
#define oo 1000000
//bool debug = false;
void calcular(int inicial, int destino, vector<int> graph[], int v,string name[]){
int dist[v];
int path[v];
bool visitado[v];
queue<int> q;
//BFS
for(int k = 0; k < v; k++){
dist[k] = -1;
path[k] = -1;
visitado[k] = false;
}
q.push(inicial);
dist[inicial] = 0;
while(!q.empty()){
int act = q.front(); q.pop();
//if(debug)cout << "Vertice: " << name[act] << "\n";
vector<int> ady = graph[act];
for(int w = 0; w < ady.size(); w++){
int k = ady[w];
//if(debug)cout << "--Adyacente: " << name[k] << "\n";
if(dist[k] == -1){
//if(debug)cout << "----Actualizo: " << dist[act]+1 << "\n";
dist[k] = dist[act]+1;
path[k] = act;
q.push(k);
}
}
}
if(dist[destino] != -1){
//if(debug)cout << "El costo es: " << dist[destino] << "\n";
int vert = path[destino];
stack<int> inv;
while(vert != -1){
//if(debug)cout << vert << "\n";
inv.push(vert);
vert = path[vert];
}
//if(debug)cout << inv.size() << "\n";
int hops = inv.size();
for(int s = 1; s <= hops; s++){
cout << name[inv.top()][0];
inv.pop();
}
cout << name[destino][0] << "\n";
}
}
int main() {
// your code goes here
int n,m,q;
string orig,dest;
cin >> n;
while(n--){
cin >> m >> q;
vector<int> graph[m+1];
cin >> orig >> dest;
map<string,int> names;
string inv[m+1];
inv[0] = orig;
inv[1] = dest;
names[orig] = 0;
names[dest] = 1;
int o = names[orig],d = names[dest];
graph[o].push_back(d);
graph[d].push_back(o);
for(int i = 2; i <= m; i++){
cin >> orig >> dest;
names[dest] = i;
inv[i] = dest;
o = names[orig],d = names[dest];
graph[o].push_back(d);
graph[d].push_back(o);
}
/*if(debug)
for(int p = 0; p < m+1; p++){
cout << p << " - " << inv[p] << " - " << names[inv[p]] << "\n";
for(int w = 0; w < graph[p].size(); w++){
cout << "---------- " << inv[graph[p][w]] << "\n";
}
}*/
for(int i = 1; i <= q; i++){
cin >> orig >> dest;
o = names[orig],d = names[dest];
//if(debug) cout << orig << " to " << dest << o << " -> " << d << "\n";
calcular(o,d,graph,m+1,inv);
}
if(n >= 1) cout << "\n";
}
return 0;
}