762 - We Ship Cheap

[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]

I think a straight Dijkstra will solve this problem with a faster time.

[Rashad]

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

[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]

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

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

[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!

[sun_kuet]

code REmoved after AC

[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]

Don't double post

[brianfry713]

Your code got RE. Try checking if the source and destination city can be found in the map.

[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.

[brianfry713]

Try running your code on the sample input.

[blackheartadhar]

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

Code: Select all

Removed After AC

[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.

[blackheartadhar]

Thanks Got Accepted.