How to optimize Dijkstra's algorithm?

Link to the problem: https://cses.fi/problemset/task/1671
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;
vector<pair<int,ll>> adj[MAXN];
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;
        adj[a].emplace_back(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;
 
        for(auto v : adj[u.second])
        {
            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 :laughing:, 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