Ho cercato di risolvere il problema SHPATH su SPOJ che è solo un'implementazione diretta dell'algoritmo di Djikstra.SPOJ SHPATH - SIGSEV Errore
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;
}
ho testato contro un sacco di casi di test da http://spojtoolkit.com/test/SHPATH
Dà la risposta corretta per tutti i casi di test. Non riesco a capire, dove si verifica l'errore di segmentazione, perché non ci sono indici di array fuori limite e nessun puntatore wild o tale.
Quindi hai un * array * di * vector * s in 'Graph'? – CinCout
Penso che potrebbe essere necessario controllare 'pqi.empty()' prima di chiamare 'top()' o 'pop()'. –
Sì, il grafico viene implementato tramite il concetto di elenco di adiacenza. E ho usato una serie di vettori per implementare questa lista di adiacenze. –