Error SPOJ SHPATH - SIGSEV

Question

I am trying to solve the SHPATH problem on SPOJ, which is just an immediate implementation of the Jikstra algorithm.

http://www.spoj.com/problems/TSHPATH/

#include <iostream> #include <map> #include <queue> using namespace std; class Graph{ public: vector< pair<int,int> > adjList[10001]; void addEdge(int city_index, int neighbor, int dist){ adjList[city_index].push_back(make_pair(neighbor,dist)); } }; struct comp{ bool operator()(const pair<int,int>& a, const pair<int,int>& b){ return a.second > b.second; } }; int dijkstra(Graph graph, int n, int source, int dest){ priority_queue< pair<int,int>, vector< pair<int,int> >, comp> pqi; map<int,int> visited; int curr_dist; vector< pair<int,int> > curr; //Start from the source pqi.push(make_pair(source,0)); while(visited.size() < n && pqi.empty == false){ //Check if it is already visited, If already visited, then ignore while(visited.find(pqi.top().first) != visited.end()){ pqi.pop(); } curr = graph.adjList[pqi.top().first]; curr_dist = pqi.top().second; //Mark it as visited visited[pqi.top().first] = curr_dist; pqi.pop(); //Visit all the neighbors for(int j=0; j<curr.size(); j++){ //If not already visited, then visit it if(visited.find(curr[j].first) == visited.end()){ pqi.push(make_pair(curr[j].first,curr_dist+curr[j].second)); } } } return visited[dest]; } int main() { int t,n,neighbors,a,b,queries; string city1,city2; string city_name; string emptyline; map<string,int> city_index; cin>>t; for(int testcase=0; testcase<t; testcase++){ Graph graph = Graph(); cin>>n; for(int city=1; city<=n; city++){ cin>>city_name; city_index[city_name] = city; cin>>neighbors; for(int neighbor=0; neighbor<neighbors; neighbor++){ cin>>a>>b; graph.addEdge(city,a,b); } } cin>>queries; for(int query=0; query<queries; query++){ cin>>city1>>city2; cout<<dijkstra(graph,n,city_index[city1],city_index[city2])<<endl; } getline(cin,emptyline); } return 0; } 

I tested it against many test boxes from http://spojtoolkit.com/test/SHPATH

It gives the correct answer for all test cases. It doesn't seem to be able to figure out where the segmentation error occurs, because there is no array index outside the bounds and no wild pointers or such.

Answer 1

In the djikstra() function, this line has been changed:

 while(visited.size() < n && pqi.empty() == false) 

Now the solution works fine for all test cases.