988  Many Paths, One Destination
Moderator: Board moderators
988  Many Paths, One Destination
Could anyone tell me what this means??
This number will always be less than 2 to the 30th.
By the way, the answer will always >= 1, right?
This number will always be less than 2 to the 30th.
By the way, the answer will always >= 1, right?
My signature:
 Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.  I HATE testing account.
 Don't send me source code for debug.
getting WA
a simple graph problem. but getting wa. i don no why. plz somebody provide some suggetions, i/o.
Code: Select all
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
#define MAXN 1000
vector <int> adj[MAXN];
int path[MAXN];
bool visited[MAXN];
int v;
int BFS()
{
int i,u,next,ret = 0;
queue <int> Q;
Q.push(0);
memset(visited,false,sizeof(visited));
memset(path,0,sizeof(path));
visited[0] = true;
path[0] = 1;
while(!Q.empty())
{
for( u = Q.front(),Q.pop(),i = 0; i < adj[u].size(); i++ )
{
next = adj[u][i];
if( !visited[next] )
{
visited[next] = true;
path[next] = path[u];
Q.push(next);
}
else path[next] += path[u];
}
}
for( i = 0; i < v; i++ ) if( adj[i].size() == 0 ) ret += path[i];
return ret;
}
int main()
{
int i,j,n,kase = 0,u;
while(scanf("%d",&v) == 1)
{
kase++;
if( kase > 1 ) putchar('\n');
for( i = 0; i < v; i++ )
{
adj[i].clear();
scanf("%d",&n);
for( j = 0; j < n; j++ )
{
scanf("%d",&u);
adj[i].push_back(u);
}
}
printf("%d\n",BFS());
}
return 0;
}
Shihab
CSE,BUET
CSE,BUET

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
Problem explanation...
Can somebody please explain what this problem asks for? I can not get the sample I/O... any explatation is welcome.
regards,
nymo
nymo

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 988  Many paths, one destination
Explanation to sample input:
You can see it becomes an DAG if you draw the choices on paper. Just count the number of all possible paths using dp.
This means from event 0 you can go to event 1,2,5. from event 1 you can go to event 2,3,4. You need to determine the number of ways you can go to event of death(event that have no choices).6
3 1 2 5
3 2 3 4
2 3 4
0
1 5
0
You can see it becomes an DAG if you draw the choices on paper. Just count the number of all possible paths using dp.
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 988  Many paths, one destination
Thanks, Shafaet...
I thought last event is the event of death... that's why I couldn't get 7 as the ans Now, I read the problem statement again and got the idea that more than one event can be counted as death... will try to solve it soon.
I thought last event is the event of death... that's why I couldn't get 7 as the ans Now, I read the problem statement again and got the idea that more than one event can be counted as death... will try to solve it soon.
regards,
nymo
nymo
Re: 988  Many Paths, One Destination
I think Input provided by SADIQ(AIUB) in udebug is not in correct form . Please remove that kind of incorrect input.
take a look carefully .. The last 3 inputs are incorrect .
Code: Select all
3
2 1 2
0
0
4
2 1 2
0
0
3 2
3
5
2 1 2
1 3
1 4
0
0
0
5
2 1 2
1 3
1 4
3 4
0