Page 3 of 4
Re: 762 - We Ship Cheap
Posted: Sun Jan 25, 2009 8:57 pm
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;
}
Re: 762 - We Ship Cheap
Posted: Fri May 28, 2010 7:33 am
by Obaida
I think a straight Dijkstra will solve this problem with a faster time.

Re: 762 - We Ship Cheap
Posted: Fri Mar 18, 2011 5:58 am
by Rashad
I am getting WA.

Can anyone please give me some i/o?? Thanks in advance.
762 - We Ship Cheap
Posted: Thu Jul 28, 2011 7:42 pm
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;
}
Re: 762 - We Ship Cheap
Posted: Sun Mar 18, 2012 10:07 am
by 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;
}
Re: 762 - We Ship Cheap
Posted: Fri Jul 20, 2012 8:54 pm
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!

762 - We Ship Cheap--Getting WA -help!
Posted: Mon Jun 17, 2013 2:46 pm
by sun_kuet
code REmoved after AC
762 - We Ship Cheap--Getting WA -help!
Posted: Mon Jun 17, 2013 2:50 pm
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;
}
Re: 762 - We Ship Cheap--Getting WA -help!
Posted: Mon Jun 17, 2013 11:29 pm
by brianfry713
Don't double post
Re: 762 - We Ship Cheap
Posted: Tue Jun 18, 2013 1:16 am
by brianfry713
Your code got RE. Try checking if the source and destination city can be found in the map.
Re: 762 - We Ship Cheap
Posted: Thu Jan 02, 2014 6:29 pm
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.
Re: 762 - We Ship Cheap
Posted: Thu Jan 16, 2014 1:30 am
by brianfry713
Try running your code on the sample input.
Re: 762 - We Ship Cheap
Posted: Thu Feb 13, 2014 4:13 pm
by blackheartadhar
Getting RE!!! Can't find any error! Please help.
Re: 762 - We Ship Cheap
Posted: Fri Feb 14, 2014 12:16 am
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.
Re: 762 - We Ship Cheap
Posted: Fri Feb 14, 2014 6:26 am
by blackheartadhar
Thanks Got Accepted.
