Ranker's blog

By Ranker, history, 3 weeks ago, In English,

I tried to solve a classic probjem by using dijkstra with set, but got TLE.

I could not find out the reason why. Here is my code: Submission 65475444

Can you suggest any reasons? Thank you!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
long long d[N];
set<pair<int, int>> st;

...
st.insert({d[u.first], u.first});
...

d has type long long. Why pair<int, int>?

»
3 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I just tinkered your solution a little bit and the reason I think you are getting TLE may be due to accessing pair elements more than once I just stored them in variables. For your curiosity, I made the same mistake xd and also you can speed this up using priority queue more here.

Modified Code

cheers :)