-B1nary-'s blog

By -B1nary-, history, 5 years ago, In English

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
  • Vote: I like it
  • -12
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use priority_queue (and don't erase old entries, just skip them later) instead of set for Q.

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

you can use priority_queue instead. std::set is too slow.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I have used priority_queue instead of std::set but I get CE in return. What should I do?

»
5 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

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.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<ll> 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<pii> 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<<i<<" ";
}
int main(){
	ll N,m;cin>>N>>m;
	for(ll i=0;i<m;i++){
		ll a,b,w;cin>>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.

»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

I think your code has a bug (error).

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I think your answer is not very helpful (useless).