All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
sohag144
New poster
Posts: 14 Joined: Mon Feb 27, 2006 4:12 pm
Location: Dhaka,Bangladesh
Contact:
Post
by sohag144 » Thu Nov 02, 2006 6:53 am
I cant understand why i got RE?
Code: Select all
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define MAXV 300
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL -1
#define INF -99
int color[MAXV+1];
int discover[MAXV+1];
int parent[MAXV+1];
int path;
queue<int> Q;
struct edge
{
vector<int> eg;
};
struct graph
{
edge e[MAXV+1];
int degree[MAXV+1];
int nvertices;
}g;
void initialize_graph()
{
int i;
g.nvertices=0;
for(i=1; i<=MAXV; i++)
{
g.degree[i]=0;
g.e[i].eg.clear();
}
//vector must be empty
}
void insert_edge(int x,int y)
{
g.e[x].eg.push_back(y);
g.degree[x]++;
}
void get_edge(char *s,int x)
{
int i,j,l,y;
char t[10];
i=0;
while(s[i]!='-')i++;
l=strlen(s);
for(i; i<l; i++)
{
if(s[i]>='0' && s[i]<='9')
{
j=0;
while((s[i]>='0' && s[i]<='9'))
{
t[j++]=s[i++];
}
t[j]=0;
y=atoi(t);
insert_edge(x,y);
}
}
}
void read_graph(int n)
{
int i;
char s[100];
initialize_graph();
g.nvertices=n;
for(i=1; i<=n; i++)
{
gets(s);
get_edge(s,i);
}
}
void bfs(int source)
{
int u,v,i;
for(u=1; u<=g.nvertices; u++)
{
color[u]=WHITE;
discover[u]=INF;
parent[u]=NIL;
}
color[source]=GRAY;
discover[source]=0;
parent[source]=NIL;
if(!Q.empty())
{
while(!Q.empty())
{
Q.pop();
}
}
Q.push(source);
while(!Q.empty())
{
u=Q.front();
Q.pop();
for(i=1; i<=g.degree[u]; i++)
{
v=g.e[u].eg[i-1];
if(color[v]==WHITE)
{
color[v]=GRAY;
discover[v]=discover[u]+1;
parent[v]=u;
Q.push(v);
}
}
color[u]=BLACK;
}
}
void find_path(int start,int end)
{
if(start==NIL || end==NIL)
{
printf("connection impossible");
path=0;
}
else if(start==end)
printf("%d ",start);
else
{
find_path(start,parent[end]);
if(path)printf("%d ",end);
}
}
void main()
{
int m,n,i,j,k,source,destination;
char s[200];
freopen("in.txt","r",stdin);
while(gets(s))
{
n=atoi(s);
if(n)
read_graph(n);
/*
for(i=1; i<=n; i++)
{
printf("%d-",i);
for(j=0; j<g.degree[i]; j++)
{
printf("%d ",g.e[i].eg[j]);
}
printf("\n");
}
*/
gets(s);
m=atoi(s);
if(m)printf("-----\n");
for(k=0; k<m; k++)
{
gets(s);
sscanf(s,"%d %d",&source,&destination);
bfs(source);
path=1;
find_path(source,destination);
printf("\n");
}
}
}
qazxcvbn
New poster
Posts: 3 Joined: Mon Feb 06, 2006 6:41 am
Post
by qazxcvbn » Thu Nov 09, 2006 5:52 pm
Code: Select all
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define len 301
int main()
{
int map[len][len];
int n,i,j,k,node,node1,count,count2;
char str[1000],*str2;
int path[len][len][100];
while(scanf("%d",&n)==1)
{
count2=0;
count=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
map[i][j]=0;
else
map[i][j]=-1;
for(k=0;k<100;k++)
{
path[i][j][k]=-1;
}
}
}
for(i=1;i<=n;i++)
{
scanf("%s",str);
strtok(str,"-");
str2=strtok(NULL,",");
while(str2!=NULL)
{
node=atoi(str2);
map[i][node]=1;
path[i][node][0]=i;
path[i][node][1]=node;
str2=strtok(NULL,",");
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(map[i][k]!=-1 && map[k][j]!=-1)
{
if(map[i][k]+map[k][j]<map[i][j] || map[i][j]==-1)
{
map[i][j]=map[i][k]+map[k][j];
count=0;
while(path[i][k][count]!=-1)
{
path[i][j][count]=path[i][k][count];
count++;
}
count2=1;
while(path[k][j][count2]!=-1)
{
path[i][j][count]=path[k][j][count2];
count++;
count2++;
}
}
}
}
}
}
scanf("%d",&n);
printf("-----\n");
for(i=0;i<n;i++)
{
scanf("%d %d",&node,&node1);
if(path[node][node1][0]==-1)
printf("connection impossible\n");
else
{
printf("%d",path[node][node1][0]);
for(j=1;j<=map[node][node1];j++)
{
printf(" %d",path[node][node1][j]);
}
printf("\n");
}
}
}
return 0;
}
I don't have any idea about what problem makes me RE.
Who can answer me???
or give me some test data.
Thanks for your help!!
faiem
New poster
Posts: 14 Joined: Fri Aug 13, 2010 12:22 pm
Post
by faiem » Thu Jan 20, 2011 7:52 am
vul sobi vul
Last edited by
faiem on Mon Mar 07, 2011 8:58 pm, edited 2 times in total.
faiem
New poster
Posts: 14 Joined: Fri Aug 13, 2010 12:22 pm
Post
by faiem » Mon Mar 07, 2011 8:53 pm
Why i got WA everytime...I think its a very simple BFS.
Code: Select all
#include<cstdio>
#include<stack>
#include<queue>
#include<set>
using namespace std;
class Net{
private:
long I,J,path[305],m,n,sou,des,test;
queue<long> Q;
stack<long> P;
set<long> s[305];
set<long>::iterator it;
bool flag[305];
public:
bool Reset(long N)
{
for(long I=0;I<=N;I++)
{
path[I]=0;
flag[I]=0;
}
while(!Q.empty())
Q.pop();
while(!P.empty())
P.pop();
return 0;
}
bool input(long node)
{
Reset(node); //reset all array;
for(long I=0;I<node;I++)
{
scanf("%ld",&m);
while(scanf("%ld",&n)==1)
{
if(n<0)
n=-n;
s[m].insert(n);
if(getchar()=='\n')
break;
}
}
scanf("%ld",&test);
printf("-----\n");
while(test--)
{
scanf("%ld %ld",&sou,&des);
BFS(sou,des);
Reset(node);
}
// print(node); //print adj_list;
return 0;
}
bool print(long N)
{
for(long I=1;I<=N;I++)
{
printf("%ld->",I);
for(it=s[I].begin();it!=s[I].end();it++)
printf("%ld ",*it);
printf("\n");
}
return 0;
}
bool graph_traversal(long node,long D)
{
for(it=s[node].begin();it!=s[node].end();it++)
{
if(flag[*it]==0)
{
Q.push(*it);
flag[*it]=1;
path[*it]=node;
if(*it==D) //if found destination return 1;
return 1;
}
}
return 0;
}
bool BFS(long S,long D) S=Source...,D=destination
{
long F,K;
Q.push(S);
flag[S]=1;
path[S]=-1;
if(S==D) //if Source = Destination
{
printf("%ld\n",S);
Q.pop();
return 0;
}
while(!Q.empty())
{
F=Q.front();
Q.pop();
if( graph_traversal(F,D) ) //if graoh _traversal return 1...that means it found the destination.
break;
}
if(flag[D]==0)
printf("connection impossible\n");
else
{
K=D;
P.push(K);
while(path[K]!=-1)
{
K=path[K];
P.push(K);
}
while(P.size()>1)
{
printf("%ld ",P.top());
P.pop();
}
printf("%ld\n",P.top());
P.pop();
}
return 0;
}
};
int main()
{
long N;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%ld",&N)==1)
{
Net Gp;
Gp.input(N);
}
return 0;
}
jakir.duet
New poster
Posts: 4 Joined: Sat Nov 20, 2010 10:27 pm
Post
by jakir.duet » Thu Apr 28, 2011 7:20 pm
Simple BFS......I did so.....but WA many times......why???
Code: Select all
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstdlib>
#include<cstring>
#define M 310
using namespace std;
int N,Path[M];
int List[M][55],adjNo[M];
bool BFS(int,int);
void PrintPath(int,int);
int main()
{
int t,i,x,y;
bool f;
freopen("in.txt","r",stdin);
while(scanf("%d",&N)==1)
{
memset(adjNo,0,sizeof(adjNo));
for(i=1;i<=N;i++)
{
scanf("%d-%d",&x,&y);
List[x][adjNo[x]++]=y;
while(scanf(",%d",&y)==1)
List[x][adjNo[x]++]=y;
}
scanf("%d",&t);
printf("-----\n");
for(i=1;i<=t;i++)
{
scanf("%d%d",&x,&y);
f=BFS(x,y);
if( f==false )
printf("connection impossible\n");
else
{
PrintPath(x,y);
printf("\n");
}
}
}
return 0;
}
bool BFS(int src,int dest)
{
int h,i,x,color[M];
queue<int>Q;
memset(color,0,sizeof(color));
color[src]=1;Q.push(src);
while(!Q.empty())
{
h=Q.front();Q.pop();
for(i=0;i<adjNo[h];i++)
{
x=List[h][i];
if(color[x]==0)
{
color[x]=1;
Path[x]=h;
if(x==dest){return true;}
Q.push(x);
}
}
}
return false;
}
void PrintPath(int x,int y)
{
if(x==y)
{
printf("%d",x);
return;
}
PrintPath(x,Path[y]);
printf(" %d",y);
}
Programming is a challenge........so as life.
sohel
Guru
Posts: 856 Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Post
by sohel » Fri Apr 29, 2011 12:41 am
Search the board first using the 'search' button/text located at the top right corner.
There are plenty of discussions for your problem. Make you post in an existing thread.
jakir.duet
New poster
Posts: 4 Joined: Sat Nov 20, 2010 10:27 pm
Post
by jakir.duet » Fri Apr 29, 2011 6:54 am
Absolutely not, there are 2/3 posts with no replies.....
Thanks Sohel vai for your responce.
Programming is a challenge........so as life.
sohel
Guru
Posts: 856 Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Post
by sohel » Fri Apr 29, 2011 10:57 am
Hm, you are right. There aren't too many discussions for this problem. However, there is one thread - so next time, try to make your post on an existing one.
jakir.duet
New poster
Posts: 4 Joined: Sat Nov 20, 2010 10:27 pm
Post
by jakir.duet » Fri Apr 29, 2011 4:51 pm
Thanks vaia again...........I'll remember your advice
Programming is a challenge........so as life.
sreka11
New poster
Posts: 15 Joined: Fri Aug 15, 2014 8:06 pm
Post
by sreka11 » Thu Sep 25, 2014 12:03 am
Can you give me some real test cases or show me why do I get a Runtime Error ?
Thanks.
Code: Select all
import java.util.*;
import java.io.*;
class Main
{
static Vector<Vector<Integer>> vect;
static int[] dist;
static int[] parent;
static int s;
static StringBuffer str;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
str = new StringBuffer();
String line = br.readLine();
while(line != null)
{
int n = Integer.parseInt(line);
vect = new Vector<Vector<Integer>>(n);
for(int i = 0; i < n; i++)
{
Vector<Integer> v = new Vector<Integer>();
vect.add(v);
}
for(int i = 0; i < n; i++)
{
line = br.readLine();
int s1;
String[] s2;
if(line.length() > 2)
{
s1 = Integer.parseInt(line.substring(0, line.indexOf('-'))) - 1;
s2 = line.substring(line.indexOf('-')+1, line.length()).split(",");
for(int j = 0; j < s2.length; j++)
{
vect.get(s1).add(Integer.parseInt(s2[j])-1);
}
}
}
line = br.readLine();
str.append("-----\n");
int n2 = Integer.parseInt(line);
for(int i = 0; i < n2; i++)
{
line = br.readLine();
StringTokenizer sTok = new StringTokenizer(line);
s = Integer.parseInt(sTok.nextToken()) - 1;
int b = Integer.parseInt(sTok.nextToken()) - 1;
Queue<Integer> q = new LinkedList<Integer>();
dist = new int[n];
parent = new int[n];
Arrays.fill(dist, -1);
q.add(s);
dist[s] = 0;
while(!q.isEmpty())
{
int v = q.poll();
Iterator it = vect.get(v).iterator();
while(it.hasNext())
{
int u = (int)it.next();
if(dist[u] == -1)
{
dist[u] = dist[v] + 1;
parent[u] = v;
q.add(u);
}
}
}
if(dist[b] != -1)
printPath(b);
else
str.append("connection impossible");
str.append("\n");
}
line = br.readLine();
}
out.write(str.toString());
out.flush();
}
public static void printPath(int v)
{
if(v == s)
{
str.append(s+1);
return;
}
printPath(parent[v]);
str.append(" " + (v+1));
}
}
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Thu Sep 25, 2014 10:46 pm
Instead of filling up a StringBuffer with all of the output try writing directly to the BufferedWriter or at least between test cases.
Check input and AC output for thousands of problems on
uDebug !
sreka11
New poster
Posts: 15 Joined: Fri Aug 15, 2014 8:06 pm
Post
by sreka11 » Thu Sep 25, 2014 11:19 pm
I am still getting a Runtime Error. I always fill the StringBuffer like this and it always works so I guess it is something else. I have tried a lot of changes but I still get Runtime Error.
moudud99
New poster
Posts: 28 Joined: Fri Feb 08, 2013 1:40 pm
Post
by moudud99 » Thu Oct 02, 2014 6:32 pm
Can someone help me with some I/O?
so that I can find my mistake.
Last edited by
moudud99 on Fri Oct 03, 2014 8:06 am, edited 1 time in total.
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Fri Oct 03, 2014 1:57 am
sreka11, try input:
Code: Select all
10
1-
2-
3-
4-
5-
6-
7-
8-
9-
10-
1
1 2
Your issue is on line 47:
s2 = line.substring(line.indexOf('-')+1, line.length()).split(",");
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
Post
by brianfry713 » Fri Oct 03, 2014 2:00 am
moudud99, don't print a space at the end of a line.
Check input and AC output for thousands of problems on
uDebug !