Блог пользователя -B1nary-

Автор -B1nary-, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
#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 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

I think your code has a bug (error).