11492 - Babel

[shiplu_1320]

Why getting WA? any critical test cases.......?

Code: Select all

/*
   Problem name: Babel
   Author      : Shiplu
   Algorithm   : Dijkstra
*/
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
struct abc
{
	int x,cost,ch;
}temp,u;
struct comp
{
	bool operator()(const abc &a,const abc &b)
	{
		return a.cost>b.cost;
	}
};
char str[4005][53];
int d[4005],inf=1077952576,m;
vector< pair <int , int> > G[4005];
int findStore(char *x)
{
	int i;
	for(i=0;i<m;i++)
		if(!strcmp(str[i],x))
			break;
	if(i==m)
		strcpy(str[m++],x);
	return i;
}
int main()
{
	int i,n,start,end,j,k,in=1<<6;
	pair<int,int> v;
	char x[55],y[55],word[4005][55];
	while(scanf("%d",&n)==1)
	{
		if(n==0)
			break;
		m=0;
		scanf("%s %s",x,y);
		start=findStore(x);
		end=findStore(y);
		memset(d,in,sizeof(d));
		for(i=0;i<4002;i++)
			G[i].clear();
		for(i=0;i<n;i++)
		{
			scanf("%s %s %s",x,y,word[i]);
			j=findStore(x);
			k=findStore(y);
			G[j].push_back(make_pair(k,strlen(word[i])));
			G[k].push_back(make_pair(j,strlen(word[i])));
		
		}
		d[start]=0;
		priority_queue<abc,vector<abc>,comp> Q;
		temp.x=start;
		temp.cost=0;
		temp.ch=0;
		Q.push(temp);
		while(!Q.empty())
		{
			u=Q.top();
			Q.pop();
			if(u.cost>d[u.x])
				continue;
			for(i=G[u.x].size()-1;i>=0;i--)
			{
				v=G[u.x][i];
				if(u.ch!=word[v.first][0]-96 && d[u.x]+v.second<d[v.first])
				{
					d[v.first]=d[u.x]+v.second;
					temp.x=v.first;
					temp.cost=d[v.first];
					temp.ch=word[v.first][0]-96;
					Q.push(temp);
				}
			}
		}
		if(d[end]<inf)
			printf("%d\n",d[end]);
		else
			printf("impossivel\n");
	}
	return 0;
}

Thanx in advance

[jan_holmes]

Try this :

Code: Select all

4
a b
a c aku
a c ku
c b kc
c b bada

It should return 5 instead of "impossivel".

[Anindya]

I can't understand why my code gets WA.
Plz someone tell me some cases where my code may fail.
I used dijkstra.Help me.Thanks in advance.

Code: Select all

Code removed after AC.

[helloneo]

Try this case..

Code: Select all

3
aaa aaa
aaa bbb x
bbb ccc yy
ccc aaa zzz
0

I don't know what the expected output would be .. But my AC code prints..

Code: Select all

0

[neilor]

Dear Anindya.

I don´t know if you correct your code, anyway the error is because a small test is missing (bold)
if(u==st)
{
x=adj;
v=x.dest;
lv=x.cost[0]-'a';
if (x.cost.size() < dis[v][lv])
dis[v][lv]=x.cost.size();
x.tot=dis[v][lv];
q.push(x);
}

if you use the same map with bellman-ford you can optimize de code to half time

Best regards

[Anindya]

Thanks a lot neilor & helloneo .
I thought that when i am updating a vertex from source,i need not to check whether this value is smaller than previous stored value.
I forgot the following line:

The same pair of languages may have several words associated to it.

From my WA it is clear that they may even have the same initial letter & that is not an error of the problemsetter.This is completely valid according to problem description.
Anyway,thanks everyone for help.

[f74956227]

Could someone plz explain how to solve this problem using dijkstra?? I can't figure out how to process the multiple edge cost...

[Chirag Chheda]

Can someone plz explain how to do the memorization using Dijkstra in this problem

[Jehad Uddin]

i m getting WA in this problem,pls help....

Code: Select all

no one replied ...
           anyway....
            got acc.....

[hotovaga]

This is my approach, I can't understand why I am getting WA.

Code: Select all

#include<iostream>
#include<utility>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>

#define MAX_INT 1077952576

using namespace std;

int E,len;

int cost[2*2000+10],res;
bool visited[2*2000+10];

map<string,int>v;
vector< vector< pair< int,pair<int,char> > > > adjList(2000*2+10);
priority_queue<pair< int,pair<int,char> > > pq;

void initialize()
{
    
	int i,j;
	
    for(i = 0; i<=E*2; i++)
		cost[i] = MAX_INT;
	
			
	for(i =0; i<=E*2; i++)
		visited[i] = false;
		
	v.clear();
	
	adjList.clear();
	
	for(i=0;i<2*E;i++)
	adjList[i].clear();
	
	pq = priority_queue<pair< int,pair<int,char> > > ();
	res = MAX_INT;
}



int main()
{
    
	int i,j,k,u,d,cnt;
	
	

	while(scanf("%d",&E)==1){
		if(E==0)
		break;
	
        initialize();
		
       string s1,s2,s3;
		
        cin>>s1>>s2;
		
		cnt = 2;
        
       
		
		v[s1] = 0;  //source vertex indexed to 0
		if(v.find(s1) == v.find(s2)){
                      res  = 0;
		              
    }
		
		v[s2] = 1; //destination vertex indexed to 1
        
		for(i=0; i<E; i++){
			s1.clear();
			s2.clear();
			s3.clear();

			
			cin>>s1>>s2>>s3;

			if(v.find(s1) == v.end()){
				v[s1] = cnt;
				u = cnt++;
			}

			else
				 u = v.find(s1)->second;

			if(v.find(s2) == v.end()){
				v[s2] = cnt;
				d = cnt++;
			}
			else
				d = v.find(s2)->second;

			len = s3.size();
		
			char ch = s3[0];

            
			adjList[u].push_back(make_pair(len,(make_pair(d,ch))));
			adjList[d].push_back(make_pair(len,(make_pair(u,ch))));
		}

		//end of taking input
//Dijkstra Begins
		cost[0] = 0;
	

	
		
		pair<int,pair<int,char> > cur, next;

		pq.push(make_pair(0,make_pair(0,'1')));
		
		

		while(!pq.empty()){
			cur = pq.top();
			pq.pop();

			cur.first = -cur.first;

			if(visited[cur.second.first])
				continue;
			visited[cur.second.first] = true;
		
			
			
			for(i = 0; i<adjList[cur.second.first].size(); i++){
                  
				next = adjList[cur.second.first][i];
				if(next.second.second == cur.second.second)
					continue;
				if(visited[next.second.first])
                    continue;

				int curcost = cost[cur.second.first] + next.first;
				
				
				if(curcost < cost[next.second.first]){
					cost[next.second.first] = curcost;
	            }
				pq.push(make_pair(-curcost,make_pair(next.second.first,next.second.second)));
			}
		}

       if( res ==0 )
           printf("0\n");
	   else if(cost[1]== MAX_INT)
			printf("impossivel\n");
		else
			printf("%d\n",cost[1]);
	}


	return 0;
}

Thanks in advance.

[SyFy]

nice problem! Solved it with Dijkstra + Java in 1.020

Used priority queue and stored in it three values (toNodeId, ch, len), where:
toNodeId - node id to which this edge goes
ch - first character of the word "on" this edge
len - current path len

the main problem I think was to guess the way to store "best paths" from start point to all other.

good luck to all!
there are NO tricky testcases.

[annisizzler]

getting wa constantly in this problem,is there anyone to help?
heres my code link:https://ideone.com/6Q8Ow
some critical i/o can also help?i have tried with all sample i/o s given here.

[Scarecrow]

annisizzler, try this I/O. Your code gives 9.

Input

Code: Select all

4
a c
c b kh
b a ku
c b akarman
b a akua
0

Output

Code: Select all

6

[asifruetcse10]

Try This Cases:

Code: Select all

3
aaa aaa
aaa bbb x
bbb ccc yy
ccc aaa zzz
11
a c
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
11
a f
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
11
a g
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
11
a d
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
0

Output Should be:

Code: Select all

impossivel
5
impossivel
8
9

[mmfrb]

Why TLE? I'm just running a normal dijsktra algorithm, and my output is correct for all the inputs in this thread.
I'd be very grateful if someone could help me. Thanks

Code: Select all

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

#define MAX 2147483645

using namespace std;

typedef pair <int, int> ii;
typedef vector <ii> vii;

vector < vii > adjList;
string s1, s2, p, start, finish;
pair < pair <string, string>, string > parents[2010];
vector <int> dist;
int i, j;
priority_queue <ii, vector <ii>, greater <ii> > pq;

int main()
{
	int m, u, d, k;
	ii front, v;
	while(scanf("%d", &m) && m)
	{
		cin >> start >> finish;
		adjList.assign(m+2, vii());
		dist.assign(m+2, MAX);
		k = 0;
		for(i = 1; i <= m; ++i)
		{
			cin >> s1 >> s2 >> p;
			if(s1 == start || s2 == start)
				adjList[0].push_back(ii(i, 0));
			if(s1 == finish || s2 == finish)
			{
				adjList[i].push_back(ii(m+1, p.length()));
				k++;
			}
			for(j = 1; j < i; ++j)
				if((s1 == parents[j].first.first || s1 == parents[j].first.second || s2 == parents[j].first.first || s2 == parents[j].first.second) && p[0] != parents[j].second[0])
				{
					adjList[i].push_back(ii(j, p.length()));
					adjList[j].push_back(ii(i, parents[j].second.length()));
				}
				parents[i] = make_pair(make_pair(s1, s2), p);
		}

		if((int)adjList[0].size() == 0 || k == 0)
		{
			printf("impossivel\n");
			continue;
		}

		dist[0] = 0;
		pq.push(ii(0, 0));

		while(!pq.empty())
		{
			front = pq.top(); pq.pop();
			u = front.second; d = front.first;

			if(dist[u] == d)
				for(int i = 0; i < (int)adjList[u].size(); ++i)
				{
					v = adjList[u][i];
					if(dist[u] + v.second < dist[v.first])
					{
						dist[v.first] = dist[u] + v.second;
						pq.push(ii(dist[v.first], v.first));
					}
				}
		}

		if(dist[m+1] == MAX) printf("impossivel\n");
		else printf("%d\n", dist[m+1]);
	}
	return 0;
}