Can't pass this graph question

Hi,
Here is the problem
https://www.hackerrank.com/challenges/beautiful-path

and this is my solution
link text

i am not abe to pass testcase 5,10,11,12,13. Can anyone help me figure out , what am i missing?

try to understand concept
https://discuss.codechef.com/questions/99664/i-want-to-learn-bfs-dfscan-someone-provide-me-stlc-implementation-of-bfs/99834

1 Like

I think you are doing the normal djikstra’s algorithm and updating the cost to reach a node to minimum at that point but here the cost function is not the same. The or operation would not work the same way. Example: If for a node v, you have choice between (5,6), you will choose 5, and there’s an edge from v with cost 2, then the optimal is to choose 6 and 2, not 5 and 2.

5 = 101

6 = 110

2 = 010

5 | 2 = 111
6 | 2 = 110

The Edge wt can be at most 2^10. I think you should attack on this constraint.

I just solved this problem my code. I was right about attacking the constraint on cost. The key observation is that the answer will be between [1,1024). You try all possible answer from 1 - 1023 and for each answer check, if you can find a path (s->e) whose OR’s of edges is equal to the answer. If yes, then that’s the answer else you check for the next answer.
If you didn’t find any answer from [1-1023] then the answer is -1.

To find all paths is an exponential problem but due to small size and not exploring useless paths (check the dfs part of my code) it works.

//