1 / 4
Apr 2020
  • If vertex removed from the queue is already visited, there is no need to process it again.
  • Store edge cost together with vertex in adjacency list (e.g., struct Edge { int vertex, int cost };), to avoid O(log n) map lookup.
  • Store adjacency using vector instead of list to avoid costly random memory access when traversing a linked list.
  • Consider using vector<bool> to improve CPU cache utilization when marking visited vertices.

Thank You so much @tjm . This was a very useful information.
It got accepted with minimum time of 1.11 sec.
Solution- https://ideone.com/74qnEC3
I did every possible change.
But i was thinking can i further make my timing better?