## 10009 - All Roads Lead Where?

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tom83
New poster
Posts: 1
Joined: Mon Nov 28, 2016 11:12 pm

### Re: 10009 - All Roads Lead Where?

Getting WA in this code, i can't find the error. I would appreciate some help.

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];
queue<int> q;
//BFS
for(int k = 0; k < v; k++){
dist[k] = -1;
path[k] = -1;
}
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;
}``````