762 - We Ship Cheap

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

Moderator: Board moderators

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 762 - We Ship Cheap

Post by tanmoy » Sun Jan 25, 2009 8:57 pm

plz someone help me i got many WA :(
here is my code

Code: Select all

#pragma warning ( disable : 4786 )
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
#define max 5000

vector<string> K(100000);
bool adj[max][max],T[max];
int node,D[max],H[max];

void Ini(string s){
	int i;
	for(i=0;i<node;i++)
		if(K[i]==s) return;
		K[node++]=s;
		return;
}

int hash(string s){
	int i;
	for(i=0;i<node;i++)
		if(K[i]==s)return i;
		return i;
}

void bfs(string s,string d){
	int i,j,k,b=0;
	i=hash(s);
	j=hash(d);
	queue<int> Q;
	Q.push(i);
	D[i]=0;
	T[i]=false;
	while(!Q.empty()){
		k=Q.front();
		Q.pop();
		for(i=0;i<node;i++)
			if(adj[k][i]&&T[i]){
				D[i]=k;
				T[i]=false;
				Q.push(i);
				if(i==j){b=1;break;}
			}
			if(b==1)break;
	}
	i=0;
	k=0;
	if(b==1){
		while(1){
			H[k++]=j;
			j=D[j];
			if(j==i)break;
		}
		for(i=k-1;i>=0;i--){
			cout<<K[D[H[i]]]<<" "<<K[H[i]];
			printf("\n");
		}
	}
	if(b==0) printf("No route\n");




}

int main(){
	char x[10],y[10];
	int i,j,g,z;
	string s,v;
	bool u=false;
		while(scanf("%d",&g)!=EOF){
			node=0;
			if(u)printf("\n");
	        memset(adj,false,sizeof(adj));
	        memset(D,0,sizeof(D));
	        memset(T,true,sizeof(T));
			for(z=0;z<g;z++){
				scanf("%s %s",x,y);
				s=x;
				v=y;
		        Ini(s);
		        Ini(v);
		        i=hash(s);
		        j=hash(v);
		        adj[i][j]=true;
		        adj[j][i]=true;
			}
			
	scanf("%s %s",x,y);
	s=x;
	v=y;		
	bfs(s,v);
	u=true;
		}
	

	return 0;
}

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 762 - We Ship Cheap

Post by Obaida » Fri May 28, 2010 7:33 am

I think a straight Dijkstra will solve this problem with a faster time. :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

Rashad
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 762 - We Ship Cheap

Post by Rashad » Fri Mar 18, 2011 5:58 am

I am getting WA. :cry: Can anyone please give me some i/o?? Thanks in advance.

rafay-hasan
New poster
Posts: 4
Joined: Sat Jul 03, 2010 1:04 pm

762 - We Ship Cheap

Post by rafay-hasan » Thu Jul 28, 2011 7:42 pm

Can anyone please help me.i got 9 RTE for this problem, and i could not found the error. no one
experienced a RTE for this problem yet in the board.thanks in advance.



#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
bool matrix[27][27],visit[680];
char a[680][5],c,d,c1,c2,g[10];
int ans[680],parent[680],line,start,destination,n;
int reset()
{
int i,j,k=0;
for(i=1;i<27;i++)
{
for(j=0;j<27;j++)
{
k+=1;
if(k<=679)
{
parent[k]=0;
ans[k]=0;
visit[k]=false;
}
matrix[j]=false;
}
}
return 0;
}
int mapping()
{
int i;
for(i=1;i<=n;i++)
{
if(a[1]==c && a[2]==d)
return i;
}
n+=1;
a[n][1]=c;
a[n][2]=d;
return n;
}
int bfs()
{
int x,i;
queue<int>q;
q.push(start);
visit[start]=true;
while(!q.empty())
{
x=q.front();
q.pop();
for(i=1;i<=n;i++)
{
if(matrix[x]==true && visit==false)
{
visit=true;
parent=x;
q.push(i);
if(i==destination)
return 0;
}
}
}
return 0;
}
int printpath()
{
int i,j,k=1,x,y;
ans[k]=destination;
j=destination;
if(visit[destination]==false)
{
printf("No route\n");
return 0;
}
if(start==destination)
{
j=destination;
printf("%c%c %c%c\n",a[j][1],a[j][2],a[j][1],a[j][2]);
return 0;
}
i=1;
while(1)
{
i=parent[destination];
//printf("%d\n",i);
k+=1;
ans[k]=i;
destination=i;
if(i==start)
break;
}
for(i=k;i>=2;i--)
{
x=ans;
y=ans[i-1];
printf("%c%c %c%c\n",a[x][1],a[x][2],a[y][1],a[y][2]);
}
return 0;
}
int main()
{
int i,x,y;
bool blank=false;
while(scanf("%d",&line)==1)
{
reset();
getchar();
if(blank)
printf("\n");
blank=true;
n=0;
for(i=1;i<=line;i++)
{
gets(g);
c=g[0];
d=g[1];
x=mapping();
c=g[3];
d=g[4];
y=mapping();
matrix[x][y]=matrix[y][x]=true;
//printf("%d %d\n",x,y);
}
gets(g);
c=g[0];
d=g[1];
start=mapping();
c=g[3];
d=g[4];
destination=mapping();
bfs();
printpath();
}
return 0;
}

User avatar
shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

Re: 762 - We Ship Cheap

Post by shaon_cse_cu08 » Sun Mar 18, 2012 10:07 am

I m also getting RTE for this problem again & agian... Plz help me to sleep soundly.... :cry: :x :(

Code: Select all

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

using namespace std;

vector<long>G[5000];

map<string,long>indx;

string a[5000];

long path[10000];

long graph_input(long edge)
{
    long i,j,node;

    string b[5000];

    char x[5],y[5];

    node=0;

    j=0;

    for(i=0; i<edge; i++)
    {
        cin>>a[j]>>a[j+1];
        j+=2;
    }

    for(i=0; i<j; i++)
    {
        b[i]=a[i];
    }

    sort(a,a+j);

    node = unique(a,a+j)-a;

    for(i=0; i<node; i++)
    {
        indx[a[i]]=i;
    }

    for(i=0; i<j; i+=2)
    {
        G[indx[b[i]]].push_back(indx[b[i+1]]);
        G[indx[b[i+1]]].push_back(indx[b[i]]);
    }

    return node;
}

int bfs(long n,long src,long dest)
{
    long k=0,i,taken[5000]= {0};

    queue<long>Q;

    Q.push(src);

    taken [src]=1;

    while(!Q.empty())
    {
        long u=Q.front();

        for(i=0; i<G[u].size(); i++)
        {
            long v=G[u][i];

            if(!taken[v])
            {
                taken[v]=1;

                path[v]=u;

                if(v==dest)
                    return 1;

                Q.push(v);
            }
        }
        Q.pop();
    }

return 0;
}

int main()
{
    //freopen("out.txt","w",stdout);

    long i,j,k,x,y,node,edge,flag=0;

    char src[5],dest[5];

    while(scanf("%ld",&edge)!=EOF)
    {
        if(flag)
            printf("\n");

        flag=1;

        node = graph_input(edge);

        scanf("%s %s",src,dest);

        if(strcmp(src,dest)==0)
            printf("%s %s\n",src,dest);

        else
        {

            k=bfs(node,indx[src],indx[dest]);

            if(k)
            {
                long destination=indx[dest],k=0,sol[10000]= {0};

                while(destination!=indx[src])
                {
                    sol[k++]=destination;

                    destination=path[destination];
                }
                sol[k++]=destination;

                while(--k>0)
                {
                    cout<<a[sol[k]]<<" "<<a[sol[k-1]]<<endl;
                }
            }
            else
                printf("No route\n");
        }

        for(i=0; i<node; i++)
        {
            G[i].clear();
        }

        indx.clear();

    }
    return 0;
}
I'll keep holding on...Until the walls come tumbling down...And freedom is all around ..... :x

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 762 - We Ship Cheap

Post by SyFy » Fri Jul 20, 2012 8:54 pm

Got AC.
Input:

Code: Select all

0
AA BB

1
AA BB
CC BB

1
AA BB
GG PP

2
AA BB
BB CC
GG GG

4
AB JK
PO LK
QW PO
LK AB
AB PO
output (with all needed newlines):

Code: Select all

No route

No route

No route



AB LK
LK PO

good luck! :D

sun_kuet
New poster
Posts: 12
Joined: Wed Mar 27, 2013 4:28 pm

762 - We Ship Cheap--Getting WA -help!

Post by sun_kuet » Mon Jun 17, 2013 2:46 pm

code REmoved after AC
Last edited by sun_kuet on Tue Jun 18, 2013 5:31 am, edited 1 time in total.

sun_kuet
New poster
Posts: 12
Joined: Wed Mar 27, 2013 4:28 pm

762 - We Ship Cheap--Getting WA -help!

Post by sun_kuet » Mon Jun 17, 2013 2:50 pm

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <string>
#include <cctype>
#include <algorithm>
#include <bitset>
#include <set>
using namespace std;

vector<int>node[100];
map<string , int > mp;
vector<int>rasta;
int parent[50000];
int bfs(int source,int termint)
{
    for(int i=0;i<5000;i++)
        parent[i] = i;
    queue<int>qu;
    qu.push(source);
    int taken[10000]={0};
    taken[source]=1;
    int reach=0;
    while(!qu.empty())
    {
        int u=qu.front();
        for(int i=0;i<node[u].size();i++)
        {
            int v=node[u][i];
            if(!taken[v])
            {
                parent[v]=u;
                taken[v]=1;
                if(v ==termint)
                {
                    while(!qu.empty())
                        qu.pop();
                    return 1;
                }
                qu.push(v);

            }
        }
        qu.pop();
    }
    return -1;
}


int find_route(int m)
{
    if(parent[m]==m)
    {
        rasta.push_back(m);
        return 0;
    }
    else
    {
        rasta.push_back(m);
        find_route(parent[m]);
    }
}
int main()
{

    int a;
    string s1,s2;
    vector<string>road_name;
    int aa=0;
    
    while(scanf("%d",&a)!=EOF)
    {
        if(aa!=0)
            cout<<endl;
        aa++;
        int j=1;
        for(int i=0;i<a;i++)
        {
            cin>>s1>>s2;
            if(mp.find(s1)==mp.end())
            {
                mp[s1]=j++;
                road_name.push_back(s1);
            }
            if(mp.find(s2)==mp.end())
            {
                mp[s2]=j++;
                road_name.push_back(s2);
            }
            node[mp.find(s1)->second].push_back(mp.find(s2)->second);
            node[mp.find(s2)->second].push_back(mp.find(s1)->second);
        }
        cin>>s1>>s2;
        int val = bfs(mp.find(s1)->second,mp.find(s2)->second);

        if(val == -1)
            cout<<"No route"<<endl;
        else
        {
            find_route(mp.find(s2)->second);
            reverse(rasta.begin(),rasta.end());
            for(int i=0;i<rasta.size()-1;i++)
                cout<<road_name[rasta[i]-1]<<" "<<road_name[rasta[i+1]-1]<<endl;
        }
        rasta.clear();
        road_name.clear();
        mp.clear();
        for(int i=0;i<100;i++)
            node[i].clear();
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 762 - We Ship Cheap--Getting WA -help!

Post by brianfry713 » Mon Jun 17, 2013 11:29 pm

Don't double post
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 762 - We Ship Cheap

Post by brianfry713 » Tue Jun 18, 2013 1:16 am

Your code got RE. Try checking if the source and destination city can be found in the map.
Check input and AC output for thousands of problems on uDebug!

moudud99
New poster
Posts: 28
Joined: Fri Feb 08, 2013 1:40 pm

Re: 762 - We Ship Cheap

Post by moudud99 » Thu Jan 02, 2014 6:29 pm

please anybody help me.I got 5 WA in this problem.help me to find any bug or anything wrong.some critical test case will be nice.
here is my code
thanks in advance.

Code: Select all

removed after AC.
Last edited by moudud99 on Wed Oct 01, 2014 7:24 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 762 - We Ship Cheap

Post by brianfry713 » Thu Jan 16, 2014 1:30 am

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

blackheartadhar
New poster
Posts: 10
Joined: Mon Nov 04, 2013 10:14 am

Re: 762 - We Ship Cheap

Post by blackheartadhar » Thu Feb 13, 2014 4:13 pm

Getting RE!!! Can't find any error! Please help.

Code: Select all

Removed After AC
Last edited by blackheartadhar on Fri Feb 14, 2014 6:27 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 762 - We Ship Cheap

Post by brianfry713 » Fri Feb 14, 2014 12:16 am

Line 60 should probably be:
for(int i=0; i<=assign; i++){
parent is cleared after each test case and then used without being resized.
Check input and AC output for thousands of problems on uDebug!

blackheartadhar
New poster
Posts: 10
Joined: Mon Nov 04, 2013 10:14 am

Re: 762 - We Ship Cheap

Post by blackheartadhar » Fri Feb 14, 2014 6:26 am

Thanks Got Accepted. :)

Post Reply

Return to “Volume 7 (700-799)”