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?

Post by tom83 » Mon Nov 28, 2016 11:17 pm

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];
	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;
}

Post Reply

Return to “Volume 100 (10000-10099)”