-B1nary-'s blog

By -B1nary-, history, 4 months 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

»
4 months 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.

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So is -B1nary- your fake account? Have I caught you Mr weng_233?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Respond with your original account than only I will believe xd

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            This is my original account.

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh shit!!! Then I have to believe you

»
4 months 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.

»
4 months 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.

»
4 months ago, # |
  Vote: I like it -19 Vote: I do not like it

I think your code has a bug (error).

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

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