762 - We Ship Cheap

[tuman]

can any one give few more i\o.
I badly need it. My code gives correct output for every input given here in electronic board. But i m still getting wrong answer. so i badly need some help.

[yogeshgo05]

code deleted..

[Sotek]

I got runtime error until I tried this input:

Code: Select all

1
AA BB
AA CC

the node CC doesn's exists so mi program looked for this and didn't find it.
if start node or end nod doesn's exists print No route

I hope it can help you to get AC

[yogeshgo05]

hi guys
i hav been getting wa , for this problem for quite some time
its just a simple bfss..
but in problem there is no mention of number of cities(nodes)
could some body tell me wat's wrong in code..
plx x give me some test cases......

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
# define MAX  1500
 using namespace std;

int s[MAX];
vector<string> v(MAX);
vector<int> d(MAX);
vector<string>dest(MAX);
int cost[MAX][MAX];
vector <int> p(MAX);

int compi(string str,int *count)
{
 	 for(int i=0;i<(*count);i++)
	 {
		  if(str==v[i])
		    return i;
	 }
	 
	 (*count)++;
	 return ((*count)-1);
}




int main()
{
 	 char a[5],b[5];
 	 int n;
 	 int i;
 	 string so,des;
 	 while(cin>>n)
 	 {		int count=0;
	     	if(n==0)
	     	{
			 		  cin>>a;
			 		  cin>>b;
			 		  cout<<"No route \n\n";
					  continue;
	     }	 		  
	     
		  for(i=0;i<n;i++)
		  {
		      cin>>a;
		      cin>>b;
		      
		      int j=compi(a,&count);
		      v[j]=a;
		      
		      int k=compi(b,&count);
		      v[k]=b;
		      
		      
		      cost[j][k]=1;
		      cost[k][j]=1;
			}
			cin>>so;
			int source=compi(so,&count);
			
			cin>>des;
			int desti=compi(des,&count);
			int z1=-1,z2=-1;
			for(i=0;i<=count;i++)
	       for(int j=0;j<=count;j++)
	       {						  if(i==j)
			 						  cost[i][j]=0;
			 						  else if(cost[i][j]!=1)
			 						  cost[i][j]=9999;
	       }
			for(i=0;i<count;i++)
			{
	          
				  if(cost[source][i]!=0 && cost[source][i]!=9999)
	           { 
				  	  z1=1;
	           }			
				   if(cost[desti][i]!=0 && cost[desti][i]!=9999)
	           { 
				  	  z2=1;
	           }
				  
				  if(z1==1 && z2==1)break;							
	  }
	  			  
					 if(z1==-1 || z2==-1){ cout<<"No route\n\n";continue;}
					 	  
			for(i=0;i<count;i++)
			{
	            p[i]=source;
					s[i]=0;
	            d[i]=cost[source][i];
			}
			s[source]=1;
			
			int r=1;
			int flag=0;
			for(int i=1;i<count;i++)
			{
	  		 		  int min1=9999;
	  		 		  int u=-1;
						  
						for(int j=0;j<count;j++)
						{
						 		  if(s[j]==0)
									{
									 		if(d[j]<min1)
											 {
											  		min1=d[j];
													  u=j;
										  }
							       }
					 }
					 
					 
					 if(u==(-1)){flag=1 ; break;}		  
		 			 s[u]=1;
		 			 
		 			 if(u==desti)break;
		 			 
		 			 for(int v=0;v<count;v++)
		 			 {
					  			if(s[v]==0)
					  			{
				 			       if(d[u]+cost[u][v]<d[v])
				 			      { d[v]=d[u]+cost[u][v];p[v]=u;}
						      }
			       }
			       
		 }
		 if(flag==0)
		 {
		  		
				  
				  int i=desti;
				  r=0;
				  
				  while(i!=source)
				  {
						dest[r++]=v[i];
						
						i=p[i];
			     }
			     
			     dest[r++]=v[source];
			     
			     for(int i=r-1;i>=1;i--)
			     {
				  			 cout<<dest[i]<<" "<<dest[i-1]<<"\n";
		        }cout<<"\n";
				       
		 }
	  else
	  		cout<<"No route\n\n";
   }
   
   return 0;
}
	  			  
 	 
 	 
			 

[yasseryahia]

I am still having RunTime Error Although I am passing all the test cases on the board

can any one help please ??

[sapnil]

I get acc by taking 1009 node(array size is 1009)
plz make sure it...

Thanks
Keep posting
Sapnil

[yasseryahia]

by the way I am using a vector to take the input and I am using BellmanFord to calculate the path not BFS (I am testing my Bellman Ford ) and this is he code

Code: Select all

#include<iostream>
#include<vector>
#include<map>
#include<string>
using namespace std;
#define oo 100000000

struct edge{
	int source,dest,cost; // source and destination and cost for the edge
	edge(){}
	edge(int s,int d,int c):source(s),dest(d),cost(c){}
};
struct node{
	int parent,dist; // the parent and the distance between the node and its parent
	node(){}
	node(int p,int d):parent(p),dist(d){}
};
/*
 * Bellman Ford ShortestPath algorithm works with negative costs but it works on edges not on points
 * edges vector must be created before calling the method
 * n is the number of nodes
*/
vector<node> BellmanFordSP(vector<edge> & edges,int source,int n){
	vector<node> nodes;
	// initializing
	int i,j;
	for(i=0;i<n;i++)
		nodes.push_back(node(-1,oo));
	nodes[source].dist = 0;
	//
	for(i=0;i<n;i++){
		bool flag = true;
		for(j=0;j<edges.size();j++){
			//Relaxation
			if(nodes[edges[j].dest].dist > nodes[edges[j].source].dist + edges[j].cost){
				flag = false;
				nodes[edges[j].dest].dist = nodes[edges[j].source].dist + edges[j].cost;
				nodes[edges[j].dest].parent = edges[j].source;
			}
		}
		if(flag) break; // No more relaxation can be done
	}
	for(i=0;i<edges.size();i++){ // To detect negative cycles
		if(nodes[edges[i].dest].dist > nodes[edges[i].source].dist + edges[i].cost){
			nodes.clear(); // Negative Cycle detected return empty vector
			break; 
		}
	}
	return nodes;
}

map<string,int> m;
map<int,string> m2;

void printPath(vector<node> v,int s,int d)
{
	if(v.size()==0){ cout<<"No route\n"; return;}

	vector<string> p;
	while(d!=s)
	{
		if(d == -1) {
			cout<<"No route\n"; return;
		}
		p.push_back(m2[d]);
		d = v[d].parent;
	}
	p.push_back(m2[s]);
	for(int i=p.size()-1;i>0;i--)
	{
		cout<<p[i]<< " "<< p[i-1]<<endl;
	}
}

int main()
{
	freopen("test.in","r",stdin);
	vector<edge> edges;
	int n;
	string str1,str2;
	int t=0;
	while(cin>>n)
	{
		if(t) cout<<"\n";
		t++;
		for(int i=0;i<n;i++)
		{
			cin>>str1>>str2;
			if(m.find(str1) == m.end())
			{
				m[str1] = m.size();
				m2[m[str1]] = str1;
			}
			if(m.find(str2) == m.end())
			{
				m[str2] = m.size();
				m2[m[str2]] = str2;
			}
			edges.push_back(edge(m[str1],m[str2],1));
			edges.push_back(edge(m[str2],m[str1],1));
		}
		cin>>str1>>str2;
		if(m.find(str1)==m.end() || m.find(str2) == m.end())
			cout<<"No route\n";
		else
			printPath(BellmanFordSP(edges,m[str1],m.size()) , m[str1],m[str2]);
		edges.clear();
		m.clear();
		m2.clear();
	}

	
	return 0;
}

so can any one help with this ??

[898989]

Hi Yasser.
Let say that your map has length 4. i mean m.size() with give 4.

lets take a look at your code.
if(m.find(str1) == m.end())
{
m[str1] = m.size();
m2[m[str1]] = str1;
}

if the code enters the condition this line "m[str1] = m.size();" will be evaluated.

This line consist of 2 parts.
1) m[str1]
2) m.size();

what value you expect your m[str1] will take? m.size() ? NO.
it will take m.size()+1

as first part "m[str1]" will be created in memory firstly, so map size will increase, then you assign its value.

No your code will not give RTE (vectors cause it when you use 1-based indexing). check your implementation for other problems.

[asmaamagdi]

Hi all,

Could someone please tell me the output for

1
AA BB
AA AA

Should it be a blank line or AA AA or what ??!!

Thnx in advance.

[898989]

I run my program, and it outputted blank line

[asmaamagdi]

Thnx Mostafa but I'm still getting WA :S. I don't know what's wrong with my code. The array size is 1500. Is it big enough ??!!
It's a simple BFS problem. I've used the same BFS function before and got some ACs with it.
Is there any trick about this problem ??!!

[898989]

I just coded Dijkstra, with no special/tricky cases & Got AC (in the past).

[turcse143]

i got AC by using BFS.
THERE are two special case:

Code: Select all

input:
1
AA BB
AA DD

1
AA BB
AA AA

output:
No route

AA AA

[Articuno]

I can't find any mistake in my code. Can anyone help me? I have got a lot of WA, my code is giving correct output for the inputs those are given here. Can anyone suggest any advice please? I will be grateful. I am giving my code, though i think it will be hard to debug as my coding approach is very poor:

Code: Select all

Removed after AC

Please someone help me to find my error. Thanks in advance.

[Articuno]

At last I have found my error. For this type of input:

Code: Select all

1
AA AA
MM MM

The output should be:

Code: Select all

MM MM

Is this some kind of joke or what?
Problem descryption says:

You may assume that the input is valid and consistent.

What can i say? I have got about 15 WA