Failing all perf testcases

I am doing a multisource bfs from the gates and updating the distance as i proceed with the BFS.
Please provide some hints.

@omkarlubal Did you try downloading the testcase and working out the bug?

yeah i tried downloading but the testcase is big :sweat_smile:

Check twice whether or not a node is visited (or whether its minimum distance is already set):

  • while pushing the neighbors of the node currently being explored,
  • when a node is popped from the queue
    If the failure is due to a time out, it’s probably because the same node is being pushed multiple times in the queue. Hope that helps

Hey @omkarlubal The formula you are using for mapping (i, j) to a single value will cause the issue.

Example : Let’s say we have a 10 * 15 matrix
Note that the index (3, 1) = 3 * 10 + 1 giving 31
also (2, 11) will also give the same result as 2 * 10 + 11 will lead to 31.

Understood the problem?
Fixing this problem would make all the tests pass.

1 Like

Closing this topic as your issue is resolved by the mentor. If it is still not resolved, Kindly un-mark the accepted solution or create a new topic and post this question as a reference link in the description of the new topic.