I was trying out the chef and reversing question of August Chanllenge. During the contest, I tried out this . My logic goes the same way as finding the path in Dijkstra’s, the only difference is I am using revcnt as the basis of relaxing the edges. (The undirected version of the graph is stored in a vector and the input graph in a set). If an edge from i to j exists in the input graph(done by finding in the set line no 42 in the code), then revcnt[j]=revcnt[i] else, revcnt[j]=revcnt[i]+1. It gave TLE.
I used map for getting the vertex with minimum revcnt, because map is a form of balanced binary tree and hance the order of insertion is O(logn) and the ver first entry of the map will give the required node to start with.
Seeing other’s solution, I tried the priority queue version of the same. It passed. Why is it so, because even in this the complexity is same I suppose. Then why the previous map solution gave tle.