# How to optimize Dijkstra's algorithm?

My Code:

``````#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MAXN = 1e5+5;
const ll INF = (1LL<<62);

int n, m;
bool vis[MAXN];
ll cost[MAXN];

int main()
{
FASTIO
memset(vis,false,sizeof(vis));
for(int i=0; i<MAXN; i++) cost[i] = INF;

cin >> n >> m;
int a, b; ll c;
for(int i=0; i<m; i++)
{
cin >> a >> b >> c;
}

cost[1] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
pq.push({0,1});
while(!pq.empty())
{
auto u = pq.top();
pq.pop();
vis[u.second] = true;

{
if(!vis[v.first])
{
if(cost[v.first] > v.second+cost[u.second])
{
cost[v.first] = v.second+cost[u.second];
pq.push({cost[v.first],v.first});
}
}
}
}
for(int i=1; i<=n; i++) cout << cost[i] << " ";
cout << "\n";

return 0;
}
``````

Even though I got an AC using the above code, I still wanted to know some optimizations I can make to reduce the running time. This code gets quite close to the time limit, it takes 0.82 seconds to run in the worst case. What are the optimizations that I can make here to bring down the running time? I donâ€™t want to get into the â€śFastest codeâ€ť leader board as of now , anything around 0.2-0.3 seconds will also be a good improvement according to me.

Good you asked, because your code is O(|V||E|). It doesnâ€™t really happen, But is much worse nonetheless. Just 1 line will make your code correct.

``````        auto u = pq.top();
pq.pop();
if(vis[u.second]) continue;
``````

Look carefully about what is happening in the queue.

Hacked.

2 Likes