Shpath tle

[aryan_0406]

question- https://www.spoj.com/problems/SHPATH/
My solution- https://ideone.com/bp7KEk

What’s wrong with my code. After so many tries also i am getting TLE.
What changes should i make?

[aryan_0406]

I also made new solution with some optimization:https://ideone.com/MQ3yTa

But still getting TLE. I am unable to find where is the problem occuring.

[tjm]

• 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.

[aryan_0406]

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/74qnEC
I did every possible change.
But i was thinking can i further make my timing better?