矢量大小的分段錯誤

我正在嘗試一個簡單的Dijkstra問題，我選擇將它的鄰接列表表示爲矢量數組，每個矢量包含一對（頂點，距離）。我這樣聲明：vector<pair<int, int> > G[MAXV];問題是，當我試圖獲得連接到給定頂點的邊的數量（即矢量的大小）時，我得到了分段錯誤。這是發生故障的線路：vectorSize=G[currentVertex-1].size();我不認爲問題是currentVertex，因爲我已經將括號之間的參數更改爲0（即第一個向量），並且仍然出現seg故障。感謝您的所有建議。下面是完整的源代碼：矢量大小的分段錯誤

#include <cstdio> 
#include <vector> 
#include <queue> 
#include <limits> 
#include <utility> 
#define MAXV 10000 
#define infinity std::numeric_limits<int>::max() 

using namespace std; 

int main() 
{ 
    vector<pair<int, int> > G[MAXV]; 
    int numCases; 
    int a, b, c; 
    int A, B; 
    int V, K; 
    bool vis[MAXV]; 
    pair<int, int> temp; 
    pair<int, int> vertexAndDistance[MAXV]; 
    priority_queue<pair<int, int>, vector< pair<int, int> >, greater<pair<int, int> > > heap; 
    pair<int, int> top; 
    int currentVertex; 
    int currentDistance; 
    int vectorSize; 

    for (int i=0; i<MAXV; i++) 
    { 
     vertexAndDistance[i].second=i+1; 
    } 

    scanf(" %d", &numCases); 
    for (int i=0; i<numCases; i++) 
    { 
     scanf(" %d %d", &V, &K); 
     for (int j=0; j<K; j++) 
     { 
      scanf("%d %d %d", &a, &b, &c); 
      temp.first=c; 
      temp.second=b; 
      G[a-1].push_back(temp); 
     } 
     scanf ("%d %d", &A, &B); 

     for (int k=0; k<V; k++) 
      vis[i]=false; 
     for (int k=0; k<V; k++) 
      vertexAndDistance[k].first=infinity; 
     vertexAndDistance[A-1].first=0; 
     heap.push(vertexAndDistance[A-1]); 

     while(true) 
     { 
      top = heap.top(); 
      currentDistance = top.first; 
      currentVertex = top.second; 
      heap.pop(); 
      if (infinity == currentDistance || B==currentVertex) break; 
//   vis[currentVertex-1]=true; 
      vectorSize=G[currentVertex-1].size(); 
      for (unsigned int k=0;!heap.empty() && k<vectorSize; k++) 
//   tr (G[currentVertex], it) 
      { 
       if (vertexAndDistance[G[currentVertex][k].second-1].first > vertexAndDistance[A-1].first + G[currentVertex][k].first) 
       { 
        vertexAndDistance[G[currentVertex][k].second-1].first = vertexAndDistance[A-1].first + G[currentVertex][k].first; 
        heap.push(vertexAndDistance[G[currentVertex][k].second]); 
       } 
      } 
     } 
     if (infinity > vertexAndDistance[B-1].first) 
      printf("%d", vertexAndDistance[B-1].first); 
     else 
      printf("NO"); 
    } 
return 0; 
}

來源

2013-11-24 rvcam

'vector > G [MAXV];'你知道這聲明瞭一個默認初始化的'std :: vector'對象的數組，它到目前爲止什麼都不包含？ –

@ g-makulik從代碼看來，OP知道這一點。但是，這樣一個令人困惑的聲明通常會導致錯誤。 –

@ g-makulik這是一對數組:) –

通常，當你有一個賽格故障，那是因爲你試圖訪問錯誤的內存區域。在這種情況下，如果G [currentVertex-1]不存在（currentVertex> max或== 0），或者heap.top返回了錯誤的值（可能爲NULL），則可能會發生這種情況。

來源

2013-11-24 17:19:02 Ice

矢量大小的分段錯誤

回答

相關問題