I was testing my implementation of Dijkstra’s shortest path on HackerEarth but my code is giving WAs on very big test cases. Can someone figure out the reason…
Link of the problem (bottom of the hakerarth page): basic implementation problem
#include <iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long ll;
typedef pair<ll , ll> p;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m,x,y,w;
cin>>n>>m;
vector<p>adj[n+1];
vector<ll> dist(n+1, 1e9);
priority_queue< p, vector <p> ,greater<p> > pq;
for(int i=0;i<m;i++)
{
cin>>x>>y>>w;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
pq.push({0,1});
dist[1] = 0;
while (!pq.empty())
{
ll u = pq.top().second;
pq.pop();
for(auto i:adj[u])
{
ll v = i.first;
ll weight = i.second;
if(dist[v]>dist[u]+weight)
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
for (int i = 2; i <=n; ++i)
{
cout<<dist[i]<<" ";
}
}