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 »

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 »

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 »

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 »

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

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

Thanks Got Accepted. :)

Post Reply

Return to “Volume 7 (700-799)”