Page 1 of 1

988 - Many Paths, One Destination

Posted: Sun Nov 26, 2006 5:59 pm
by ..
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?

Posted: Sun Nov 26, 2006 6:26 pm
by sohel
This number will always be less than 2 to the 30th.

I interpreted, "this number will be less than 2^30", not sure though... :-?

Yes, answer will always be atleast 1, since we all have to die some day :( , so there is atleast one path.

Posted: Sun Nov 26, 2006 6:57 pm
by ..
Thanks :D

Posted: Sun Nov 26, 2006 8:19 pm
by Emilio
This number will always be less than 2 to the 30th.
That sentece is a direct translation, and its meaning is 2^30. ALthough i think that translation is not correct.

getting WA

Posted: Tue May 22, 2007 10:25 pm
by shihabrc
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;
}


Posted: Thu Jul 05, 2007 6:04 pm
by jan_holmes
Can anybody tell me what is the limit of n ? And I think it is a dp problem, am I right ?

EDIT : ACC... :) The one for sure is that n < 15000. And yes, it is kind of a dp problem ( at least I solved it that way).

Problem explanation...

Posted: Mon Aug 06, 2007 11:00 am
by nymo
Can somebody please explain what this problem asks for? I can not get the sample I/O... any explatation is welcome.

Re: 988 - Many paths, one destination

Posted: Mon Jun 06, 2011 9:52 pm
by Shafaet_du
Explanation to sample input:
6
3 1 2 5
3 2 3 4
2 3 4
0
1 5
0
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).

You can see it becomes an DAG if you draw the choices on paper. Just count the number of all possible paths using dp.

Re: 988 - Many paths, one destination

Posted: Thu Jun 30, 2011 2:39 pm
by nymo
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.

Re: 988 - Many Paths, One Destination

Posted: Mon Jan 11, 2016 7:18 am
by anando_du
I think Input provided by SADIQ(AIUB) in udebug is not in correct form . Please remove that kind of incorrect input.

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
take a look carefully .. The last 3 inputs are incorrect .