762 - We Ship Cheap

[nexttw]

I got the RTE.Please help me.I had test the city AA to ZZ. There are 26*26 cities.

#include<iostream>
#include<fstream>
#include<string>
#include<queue>
#include<stack>
using namespace std;
string city_num[700];
int num_total_city;
bool m[700][700],inside,findend=0;
queue<int> q;
stack<string> p;
int father[700],from_num,to_num;
int searching(string s){
int i;
for(i=0;i<num_total_city;i++){
if(city_num==s){
return i;
}
}
return -1;
}
void bfs(int i){
int j;
if(i<0) return;
for(j=0;j<num_total_city;j++){
if(m[j]){
if(father[j]==-1) father[j]=i;
if(j==to_num){
findend=true;
return;
}
q.push(j);
m[j]=false;
}
}
while(!q.empty()){
i=q.front();
for(j=0;j<num_total_city;j++){
if(m[j]){
if(father[j]==-1) father[j]=i;
if(j==to_num){
findend=true;
return;
}
q.push(j);
m[j]=false;
}
}
q.pop();
}
}
int main()
{
ifstream fin;
fin.open("7.txt");
istream& input(cin);
ofstream fout;
fout.open("5.txt");
int i,j,num1,num2,n;
string city[1400],from,to;
char x;

while(input>>n){
for(i=0;i<700;i++){
for(j=0;j<700;j++){
m[j]=false;
}
}
while(!p.empty()) p.pop();
while(!q.empty()) q.pop();
findend=false;
for(i=0;i<700;i++){
city_num="";
father=-1;
}
for(i=0;i<1400;i++){
city="";
}

for(i=0;i<n*2;i++){
input>>city;
}
input>>from>>to;
num_total_city=0;
for(i=0;i<n*2;i++){
inside=false;
for(j=0;j<num_total_city;j++){
if(city[i]==city_num[j]){
inside=true;
}
}
if(!inside){
city_num[num_total_city]=city[i];
num_total_city++;
}
}
for(i=0;i<n*2;i=i+2){
num1=searching(city[i]);
num2=searching(city[i+1]);
m[num1][num2]=true;
m[num2][num1]=true;
}
/*for(i=0;i<num_total_city;i++){
for(j=0;j<num_total_city;j++){
fout<<m[i][j];
}
fout<<endl;
}*/
from_num=searching(from);
to_num=searching(to);
bfs(from_num);
p.push(to);
i=to_num;
while(father[i]!=-1){
i=father[i];
p.push(city_num[i]);
}
//p.push(from);
if(!findend&&to!=from){
cout<<"No route"<<endl;
}
if(findend){
while(!p.empty()){
cout<<p.top()<<" ";
p.pop();
cout<<p.top()<<endl;
if(p.size()==1) break;
}
}
cout<<endl;
}
return 0;
}

[brianfry713]

Don't open files.

[alecassis]

Can anybody help me?
I'm getting WA and I've passed every test case discussed in this thread.

Code: Select all

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;


map<int, vi> graph;
map<string, string> parent;
map <string, int> indexes;
map <int, string> cities;

void backtrack(string begin, string end) {
	stack<string> path;
	string x = end;
	while (true) {
		if (parent.count(x)) {
			path.push(x);
			x = parent[x];
		}
		else break;
	}
	string last;
	for (int i = 0; i < (int)path.size(); i++) {
		cout << parent[path.top()] << " " << path.top() << endl;
		last = path.top();
		path.pop();
	}
	if (last != end)
		cout << last << " " << end << endl;
 
 }


int main () {
	int t, cont = 0;
	
	while (scanf("%d", &t) != EOF) {
		if (cont)
			printf("\n");
		int idx = 0;
		graph.clear();
		indexes.clear();
		parent.clear();
		cities.clear();
		for (int i = 0; i < t; i++) {
			string a, b;
			cin >> a >> b;
			if (!indexes.count(a)) {
				indexes[a] = idx;
				cities[idx] = a;
				idx++;
			}
			if (!indexes.count(b)) {
				indexes[b] = idx;
				cities[idx] = b;
				idx++;
			}
			graph[indexes[a]].push_back(indexes[b]);
			graph[indexes[b]].push_back(indexes[a]);
		}

		string init, dest;
		cin >> init >> dest;
		if (init == dest) {
			cout << init << " " << dest << endl;
			cont++;
			continue;
		}
		if (!indexes.count(init)) {
			printf("No route\n");
			cont++;
			continue;
		}
		int begin = indexes[init];
		int end = indexes[dest];
		queue<int> q;
		q.push(begin);
		map<int, int> dist;
		dist[begin] = 0;
		bool found = false;

		while (!q.empty() && !found) {
			int u = q.front();
			q.pop();
			for (int i = 0; i < (int)graph[u].size(); i++) {
				int v = graph[u][i];
				if (!dist.count(v)) {
					dist[v] = dist[u] + 1;
					q.push(v);
					parent[cities[v]] = cities[u];
					if (v == end) {
						found = true;
						break;
					}
				}
			}
		}
		if (found) {
			backtrack(init, dest);
		}
		else
			printf("No route\n");
		cont ++;
	}

	return 0;
}

thanks in advance

[brianfry713]

Input:

Code: Select all

1
AA BB
BB CC

AC output No route

[hamim32]

Why getting RE!!!please help
I've tested all the inputs discusssed in this forum

Code: Select all

#include<bits/stdc++.h>
using namespace std;
map<string,int>m;
vector<int>v[100];
int visited[100];
int parent[100];
vector<int>sv;
vector<string>ss;
void bfs(int src,int d)
{
    queue<int>q;

   memset(visited,-1,sizeof(visited));
   memset(parent,-1,sizeof(parent));

   visited[src]=0;
   q.push(src);
   int u,r;
   while(!q.empty())
   {
     int a=q.front();
      q.pop();
    for(int i=0;i<v[a].size();i++)
  {

    u=v[a][i];
     if(visited[u]==-1)
    {
        visited[u]=visited[a]+1;
        parent[u]=a;
        q.push(u);
    }
    if(u==d)break;
  }

}
if(visited[d]==-1){cout<<"No route"<<endl;return;}
  r=d;
  sv.push_back(r);
  r=parent[r];
  while(r!=src)
  {
      sv.push_back(r);
  r=parent[r];
  }
  sv.push_back(r);
  reverse(sv.begin(),sv.end());
  for(int i=0;i<sv.size()-1;i++)
    cout<<ss[sv[i]]<<" "<<ss[sv[i+1]]<<endl;

}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s,s1;
 char x,y,z;
 int l=0,i,edge;

bool p=0;
while(scanf("%d",&edge)!=EOF)
    {
    	//if(edge==0){cin>>s>>s1;continue;}
        l=0;
   if(p)cout<<endl;
     for(int k=0;k<edge;k++)
     {
         cin>>s>>s1;
         if(m.find(s)==m.end()){m[s]=l;ss.push_back(s);l++;}
         if(m.find(s1)==m.end()){m[s1]=l;ss.push_back(s1);l++;}

         v[m[s]].push_back(m[s1]);
         v[m[s1]].push_back(m[s]);
     }
     cin>>s>>s1;
     if(s==s1)cout<<s<<" "<<s1<<endl;
    else if(m.find(s)==m.end()||m.find(s1)==m.end())cout<<"No route"<<endl;
    else bfs(m[s],m[s1]);

     ss.clear();
     m.clear();
     for(int k=0;k<100;k++)v[k].clear();
     sv.clear();
     p=true;
     getchar();
    }
    //else return 0;


   return 0;
 }

[mbstu_nitai]

Why I am getting WA
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000
map<string,ll>mp;
map<ll,string>mp2;
bool vis[100005];
ll dis[100005];
vector<ll>vec[100005];
ll par[100005];

void bfs(ll uu)
{
queue<ll>Q;
Q.push(uu);
dis[uu] = 0;
while(!Q.empty())
{
ll u = Q.front();
Q.pop();
for(ll i = 0; i<vec.size(); i++)
{
ll v = vec;
if(dis[v] == inf)
{
dis[v] = dis + 1;
par[v] = u;
Q.push(v);

}
}
}
}

int main()
{
// freopen("in.txt","rt",stdin);
//freopen("out.txt","wt",stdout);
ll node,cn = 0;
while(scanf("%lld",&node) == 1)
{
if(cn>0) cout<<endl;
cn++;

ll i = 0,nod = node;
string a,b;
ll kk = node;
while(nod--)
{
cin>>a>>b;
if(mp[a] == 0)
{
i++;
mp[a] = i;
mp2 = a;
}

if(mp == 0)
{
i++;
mp = i;
mp2 = b;
}

vec[mp[a]].push_back(mp);
vec[mp].push_back(mp[a]);
}

cin>>a>>b;
if(a == b)
{cout<<a<<" "<<a<<endl;
continue;
}
else if(mp[a] == 0 || mp == 0)
{
cout<<"No route"<<endl;
continue;
}
par[mp[a]] = -1;
for(ll i=0; i<=100003; i++)dis=inf;
bfs(mp[a]);
if(dis[mp] == inf) cout<<"No route"<<endl;
else
{
vector<ll>path;

ll x = mp;
path.push_back(x);
while(par[x]!=-1)
{
path.push_back(par[x]);
x = par[x];
}
reverse(path.begin(),path.end());
cout<<mp2[path[0]]<<" "<<mp2[path[1]]<<endl;
if(path.size()>2)
{
for(ll k = 2; k<path.size(); k++)
cout<<mp2[path[k-1]]<<" "<<mp2[path[k]]<<endl;
}
}
for(ll k = 0; k<=100003; k++)
vec[k].clear();
mp.clear();
mp2.clear();
}

return 0;
}
/*
3
JV PT
KA PT
KA HP
JV HP


2
JV PT
KA HP
JV HP

*/

[lighted]

Your code gets compile error.