Help with SPOJ EZDIJKST


#1

Can anyone please tell me what’s wrong with my solution.

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

int main(){

int t;
cin>>t;
while(t--){
    
int n,e,u,v,dis,i,xx,yy;
cin>>n>>e;

unordered_map<int, list<pair<int,int> > > m;

for(i=0; i<e; i++){
    cin>>u>>v>>dis;
    m[u].push_back(make_pair(v,dis));
    m[v].push_back(make_pair(u,dis));
}

cin>>xx>>yy;

map<int,int> dist;

for(i=0; i<n; i++)
dist[i+1] = INT_MAX;

set<pair<int, int> > s;

dist[xx] = 0;
s.insert(make_pair(0,xx));

while(!s.empty()){

    auto p =   *(s.begin());
    int node = p.second;

    int nodeDist = p.first;
    s.erase(s.begin());

    for(auto childPair: m[node]){

        if(nodeDist + childPair.second < dist[childPair.first]){

            int dest = childPair.first;
            auto f = s.find( make_pair(dist[dest],dest));
            if(f!=s.end()){
                s.erase(f);
            }

            dist[dest] = nodeDist + childPair.second;
            s.insert(make_pair(dist[dest],dest));
        }
    }
}

if(dist[yy]!=INT_MAX)
cout<<dist[yy]<<endl;
else
cout<<"NO"<<endl;
    
dist.clear();
s.clear();

m.clear();

}

return 0;
}


#2

Next time when you are asking for help, make sure that the code formatting is correct and also provide a link to the problem.

I read your code a couple of times and I couldn’t find a bug. Then I read the problem statement and found your mistake.

The graph in the problem is a directed one.

Just change one line and you will be good to go. :slight_smile:


#3

@rgkbitw thank you :slight_smile: