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?

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

[..]

Thanks

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

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

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

[nymo]

Can somebody please explain what this problem asks for? I can not get the sample I/O... any explatation is welcome.

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

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

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