c++ - vector 大小的段错误

Question

我正在尝试一个简单的 Dijkstra 问题，我选择将我的邻接列表表示为一个 vector 数组，每个 vector 包含一对(顶点，距离)。我是这样声明的:vector<pair<int, int> > G[MAXV];问题是，当我尝试获取连接到给定顶点的边数(即 vector 的大小)时，我遇到了段错误。这是发生故障的行:vectorSize=G[currentVertex-1].size();我不认为问题出在 currentVertex 上，因为我已经将括号之间的参数更改为 0(即第一个 vector )，但我仍然遇到段错误。感谢所有建议。这是完整的源代码:

#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;
}

Answer 1

通常当你遇到段错误时，那是因为你试图访问错误的内存区域。在您的情况下，如果 G[currentVertex-1] 不存在(currentVertex > max 或 ==0)或者 heap.top 返回错误值(可能为 NULL)，则可能会发生这种情况