ベクトルのベクトルにプッシュするときのC++のsigabrt

Question

私はDjikstraアルゴリズムを使ってグラフ内の特別なパスを検索する小さなプログラムに取り組んでいます。アルゴリズム的には正しいです - 私はそれについて100％確信しています。基本的には、通常のDjikstraの唯一の変更は、エッジの値がペアである場合に特別な方法で比較されることです。また、Djikstraは2つのパス長を返します。

タスクと詳細は重要ではありません。なぜなら、私のプログラムは完全に無関係な何らかの理由で失敗するため、なぜ見つからないのでしょうか？入力を読み込んで構造体に入れるときに失敗します。

入力形式は次のとおりです。n =頂点数、m =エッジ数、q =質問数。 edge：vertex1、vertex2、value、charValueの記述があるm行よりNまたはBです。その後、startとendの間の最短パスを尋ねるq個の質問があります。

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 

：私の入力はこのようになったときに、私は、入力の最後の行に取り組ん中にライン97上の

SIGABRT free(): invalid pointer: 0x000000000060b0d0 

を（ポインタの数はもちろんのすべての時間は異なります）一back上 （）取得しています

（入力が完了していない - まだいくつかのエッジがあり、質問もありますが、常に同じ場所で失敗します）

私は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); 
}