### -B1nary-'s blog

By -B1nary-, history, 4 months ago, ,

Hello everyone, I was solving this Problem 20C - Dijkstra? and wrote a code and submitted but it gave me a TLE on test 28. Can I still improve my code's efficiency? I am not able to figure it out how to do so. Thanks.

My code

• -12

 » 4 months ago, # |   0 Use priority_queue (and don't erase old entries, just skip them later) instead of set for Q.
 » 4 months ago, # |   +11 you can use priority_queue instead. std::set is too slow.
•  » » 4 months ago, # ^ |   +3 I have used priority_queue instead of std::set but I get CE in return. What should I do?
•  » » » 4 months ago, # ^ |   0 So is -B1nary- your fake account? Have I caught you Mr weng_233?
•  » » » » 4 months ago, # ^ |   0 No.
•  » » » » » 4 months ago, # ^ |   0 Respond with your original account than only I will believe xd
•  » » » » » » 4 months ago, # ^ |   0 This is my original account.
•  » » » » » » » 4 months ago, # ^ |   0 Oh shit!!! Then I have to believe you
 » 4 months ago, # | ← Rev. 3 →   +16 Priority queue can be a bit faster but using set and erasing elements is fine too, I always do it.Switch order in pair (vertex, dist) to (dist, vertex). Your current solution sorts by vertex id. This is quadratic or maybe even exponential. And don't forget about long long and bigger inf because distances can get big.
•  » » 4 months ago, # ^ |   0 Oh i see. Thank you for this info.
 » 4 months ago, # | ← Rev. 2 →   0 #include using namespace std; typedef long long ll; typedef pair pii; typedef vector vii; typedef vector vi; #define inf ll(1e16) vii G[100500]; vi D,P; void Dijkstra(ll s,ll N){ D.assign(N+1,inf); P.assign(N+1,-1); D[s]=0; priority_queue Q; Q.push({0,s}); while(!Q.empty()){ auto tp=Q.top(); Q.pop(); ll u=tp.second; ll weight = -tp.first; if(weight>D[u]) continue; for(auto next:G[u]){ ll v=next.first,wt=next.second; if(D[v]>weight+wt){ P[v]=u; D[v]=weight+wt; Q.push({-D[v],v}); } } } } void print_shortest_path(ll to){ vi path; for(ll i=to;i!=-1;i=P[i])path.push_back(i); reverse(path.begin(),path.end()); for(auto i:path)cout<>N>>m; for(ll i=0;i>a>>b>>w; if (a == b) continue; G[a].push_back({b,w}); G[b].push_back({a,w}); } Dijkstra(1,N); if(D[N]==inf)cout<<-1; else print_shortest_path(N); } There is your code. But slightly modified.
•  » » 4 months ago, # ^ |   0 Thank you. This worked.
 » 4 months ago, # |   -19 I think your code has a bug (error).
•  » » 4 months ago, # ^ |   +21 I think your answer is not very helpful (useless).