C++ sigabrt推向矢量

Question

我正在使用Djikstra算法在图中搜索特殊路径的小程序。算法上它是正确的 - 我对此100％确定。基本上，对正常Djikstra的唯一修改是当边的值是对时，它们以特殊方式进行比较。另外，Djikstra返回2个路径长度。

这里的任务和细节并不重要，因为我的程序由于与它完全无关的事情而失败，我似乎无法找到原因。读取输入并将其放入结构时失败。

输入格式如下：n =顶点数，m =边数，q =问题数。比描述边的m行要多：vertex1，vertex2，value，charValue是N还是B.之后有q个问题询问起始和结束之间的最短路径。我越来越

SIGABRT free(): invalid pointer: 0x000000000060b0d0 

（指针的数量是不同的，当然所有的时间）上线97上的push_back（） 输入的最后行工作期间，当我输入的是这样的：

6 11 5 
0 1 6 B 
0 3 5 N 
0 3 10 B 
0 4 0 N 
0 5 2 B 
5 2 7 N 
5 4 1 B 
4 1 3 N 

（输入未完成 - 仍然有一些边缘和问题，但它始终在相同的地方失败）

我试过Valgrind没有成功。代码是这样的：

#include <iostream> 
#include <vector> 
#include <limits> 
#include <set> 
using namespace std; 

struct myStruct{ 
    long long n,b; 
    int vertex; 
}; 

struct comparator { 
    bool operator() (const myStruct& left, const myStruct& right) const{ 
     if (left.n == right.n){ 
      return left.b < right.b; 
     } else { 
      return left.n < right.n; 
     } 
    } 
}; 

pair<long long, long long> customDjikstra(int start, int end, int n,vector< vector<myStruct> > &graf){ //djikstra 
    vector<pair<long long,long long> > djikstraLengthPaths; 
    set< myStruct , comparator > orderedSet; 
    djikstraLengthPaths.reserve(n); 
    for(int i = 0; i < n; i++){ 
     djikstraLengthPaths.push_back(make_pair(numeric_limits<long long>::max(),numeric_limits<long long>::max())); 
    } 
    djikstraLengthPaths[start].first = 0; 
    djikstraLengthPaths[start].second = 0; 
    vector<bool> visited; 
    visited.resize(n); 
    myStruct tmp,currentVertex; 
    tmp.b = 0; 
    tmp.n = 0; 
    tmp.vertex = start; 
    orderedSet.insert(tmp); 

    while(!orderedSet.empty()){ 
     currentVertex = (*orderedSet.begin()); 
     orderedSet.erase(orderedSet.begin()); 
     if (visited[currentVertex.vertex]){ 
      continue; 
     } 
     visited[currentVertex.vertex] = true; 

     for(int j = 0; j < graf[currentVertex.vertex].size();j++){ 
      myStruct edge = graf[currentVertex.vertex][j]; 

      if(djikstraLengthPaths[edge.vertex].first > currentVertex.n + edge.n || (djikstraLengthPaths[edge.vertex].first == currentVertex.n + edge.n && djikstraLengthPaths[edge.vertex].second > currentVertex.b + edge.b)){ //ak to zlepsi hodnotu nasej cesty, updatneme to 
       djikstraLengthPaths[edge.vertex].first = currentVertex.n + edge.n; 
       djikstraLengthPaths[edge.vertex].second = currentVertex.b + edge.n + edge.b; 

       tmp.n = djikstraLengthPaths[edge.vertex].first; 
       tmp.b = djikstraLengthPaths[edge.vertex].second; 
       tmp.vertex = edge.vertex; 
       orderedSet.insert(tmp); 
      } 
     } 

    } 

    return djikstraLengthPaths[end]; 

} 

int main() { 
    int n,m,q; 
    cin >> n >> m >> q; 
    vector<vector<myStruct> > graf(n); 
    myStruct temp; 
    int a,b,c; 
    char d; 
    bool flag; 
    for(int f = 0; f < m;f++){ 
     int i; 
     cin >> a >> b >> c >> d; 
     flag = 0; 
     /*Graph is list of neighbours*/ 
     for(i = 0; i < graf[a].size();i++){ 
      if(graf[a][i].vertex == b){ 
       flag = 1; 
       break; 
      } 
     } 

     if(d == 'N'){ 

      if(!flag){ 
       temp.n = c; 
       temp.b = 0; 
       temp.vertex = b; 
       graf[a].push_back(temp); 
       temp.n = c; 
       temp.b = 0; 
       temp.vertex = a; 
       graf[b].push_back(temp); 
      } else if(graf[a][i].n > c) { 
       graf[a][i].n = c; 
       graf[a][i].b = 0; 
       graf[b][i].n = c; 
       graf[b][i].b = 0; 
      } 

     }else { 
      if(!flag){ 
       temp.n = 0; 
       temp.b = c; 
       temp.vertex = b; 
       graf[a].push_back(temp); 
       temp.n = 0; 
       temp.b = c; 
       temp.vertex = a; 
       graf[b].push_back(temp); 
      } else if(graf[a][i].n > 0 || graf[a][i].b > c) { 
       graf[a][i].n = 0; 
       graf[a][i].b = c; 

       graf[b][i].n = 0; 
       graf[b][i].b = c; 

      } 
     } 
    } 

    int start,end; 
    pair<long long, long long> answer; 

    for(int j = 0; j < q;j++){ 
     cin >> start >> end; 
     answer = customDjikstra(start,end,n,graf); 
     if(answer.first == numeric_limits<long long>::max()){ 
      cout << "-1 -1" << endl; 
     } else { 
      cout << answer.first << ' ' << answer.second << endl; 
     } 
    } 
} 

如果你能帮助我，告诉我什么我做错了，忘了初始化或类似的东西，这将是巨大的。

Answer 1

int main() { 
int n,m,q; 
cin >> n >> m >> q; 
vector<vector<myStruct> > graf(n); 
myStruct temp; 
int a,b,c; 
char d; 
bool flag; 
for(int f = 0; f < m;f++){ 
    int i; 
    cin >> a >> b >> c >> d; 
    flag = 0; 
    /*Graph is list of neighbours*/ 
    for(i = 0; i < graf[a].size();i++){ 
     if(graf[a][i].vertex == b){ 
      flag = 1; 
      break; 
     } 
    } 

你不格拉夫if(graf[a][i].vertex == b) 你是出界的调整内向量。您需要将内部矢量调整为正确的长度，如

for(int i =0;i<n;i++) 
{ 
    graf[i].resize(size_var); 
}