Can't pass this graph question

Here is the problem

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

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.