SPOJ SHPATH - SIGSEV Fehler

Question

Ich habe versucht, das SHPATH-Problem auf SPOJ zu lösen, das nur eine direkte Implementierung von Djikstras Algorithmus ist.

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; 
} 

ich es gegen eine Menge von Testfällen aus http://spojtoolkit.com/test/SHPATH die richtige Antwort Es gibt

für alle Testfälle getestet haben. Ich kann nicht herausfinden, wo der Segmentierungsfehler auftritt, weil es keinen Array-Index außerhalb der Grenzen und keine Wild-Pointer oder ähnliches gibt. Jetzt

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

wird die Lösung läuft gut, für alle Testfälle:

Answer 1

In der Funktion djikstra() wurde diese Linie geändert.