c++ - dijkstra implememtation giving wrong outputs -

i trying solve problem understanding of dijkstra algorithm .this mentioned problem : https://www.hackerrank.com/challenges/dijkstrashortreach . first testcase accepted others wrong.please hint me wrong implementation . far understand algorithm have implemented correctly

here code:

#include<bits/stdc++.h> using namespace std; #define max 100001 #define inf int_max #define pii pair< int, int > #define pb(x) push_back(x)  int main() { int i, u, v, w, sz, nodes, edges, starting; int t; cin>>t; while(t--){     priority_queue< pii, vector< pii >, greater< pii >  > q;     vector< pii > g[max];     int d[max];     bool f[max];     // create graph     scanf("%d %d", &nodes, &edges);     for(i=0; i<edges; i++) {         scanf("%d %d %d", &u, &v, &w);         g[u].pb(pii(v, w));         g[v].pb(pii(u, w)); // undirected     }     scanf("%d", &starting);     // initialize distance vector     for(i=1; i<=nodes; i++) { d[i] = inf; f[u] = 0;}     d[starting] = 0;     q.push(pii(starting, 0));     // dijkstra     while(!q.empty()) {         u = q.top().first;         q.pop();         if(f[u]) continue;         sz = g[u].size();         for(i=0; i<sz; i++) {             v = g[u][i].first;             w = g[u][i].second;             if(!f[v] && d[u]+w < d[v]) {                     d[v] = d[u] + w;                     q.push(pii(v, d[v]));             }         }         f[u] = 1; // done u     } // result     for(i=1; i<=nodes; i++){         if(i!=starting){         if(d[i]==inf)printf("%d ",-1);         printf("%d ",d[i]);     }   } } return 0; } 

your min heap not correct, need define comparison function pair. using greater not enough.

this comparison c++ using pair,

template <class t1, class t2>   bool operator<  (const pair<t1,t2>& lhs, const pair<t1,t2>& rhs) { return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); } 

you can see that, compares first second, ideal behavior should compared second before first (as in case, first node id, , second weight). more details, please here

or, can reverse position of first , second in pair.

one more problem

for(i=1; i<=nodes; i++) { d[i] = inf; f[u] = 0;} 

should be:

for(i=1; i<=nodes; i++) { d[i] = inf; f[i] = 0;} 

last problem is, each new test case, need print result in new line, plus, last if condition not correct. should be:

for(i=1; i<=nodes; i++){     if(i!=starting){         if(d[i]==inf)             cout << -1 << " ";         else                 cout << d[i] << " ";     } } cout << endl;   

my code has been accepted after changes.