Próbowałem rozwiązać problem SHPATH na SPOJ, który jest tylko bezpośrednią implementacją algorytmu Djikstry.SPOJ SHPATH - SIGSEV Error
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;
}
Ja testowałem go przed wieloma testami z http://spojtoolkit.com/test/SHPATH
To daje poprawną odpowiedź dla wszystkich testami. Nie wydaje się, aby dowiedzieć się, gdzie występuje błąd segmentacji, ponieważ nie ma indeks tablicy poza granicami i nie ma dzikich wskaźników lub takich.
Więc masz * tablicę * z * wektorów * w 'Wykresie'? – CinCout
Myślę, że możesz potrzebować sprawdzić 'pqi.empty()' przed wywołaniem 'top()' lub 'pop()'. –
Tak, wykres jest realizowany za pomocą koncepcji listy przyległości. Użyłem wielu wektorów do implementacji tej listy sąsiedztwa. –