I was solving problem https://codeforces.com/problemset/problem/601/A in which I was using simple BFS but I took MLE on test 57, but when I changed the way of marking visited node slightly it got accepted. Can anyone help me to understand the reason for this ?
This approach was Accepted. https://codeforces.com/contest/601/submission/55706140
This approach gave MLE https://codeforces.com/problemset/submission/601/55703452
The only difference is in the way how I mark visited node.
Thank You !!
You marked visited node when you already pop it, but in this moment there may be several more in queue(in additional you dont check if you already pop this node) and your code pop this node again. But in Accepted submission you marked node after first pushing and there can be only one node in queue
You may add
if(vis[u.F]) continue;when poping https://codeforces.com/problemset/submission/601/55707981Thank You !! I got the point .