Link to the problem: CSES - Shortest Routes I
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 , anything around 0.2-0.3 seconds will also be a good improvement according to me.