提问者:小点点

使用BFS算法时出现运行时错误


有n个城市由m个航班连接。 每个航班从城市u出发,到达v,价格为W。

现在给出所有的城市和航班,连同起始城市src和目的地dst,你的任务是找到从src到dst最多k站的最便宜的价格。 如果没有这样的路由,输出-1。

例如:

例1:

输入:

n=3,

边沿=[[0,1,100],[1,2,100],[0,2,500]]

src=0,dst=2,k=1

输出:200说明:图是这样的:

下面是我的代码:

class Solution {
public:
    int ans=INT_MAX;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<vector<int>>>g;
        for(auto f:flights)
        {
            int from=f[0];
            int to=f[1];
            int cost=f[2];
            g[from].push_back({to,cost});
        }
        queue<vector<int>>q;
        q.push({src,0,-1});
        while(!q.empty())
        {
             vector<int>curr=q.front();
            q.pop();
            int currCity=curr[0];
            int currCost=curr[1];
            int currK=curr[2];
            
            if(currCity == dst)
            {
                ans=min(currCost,ans);
                continue;
            }
            for(auto x:g[currCity])
            {
                if(currK+1<=K && currCost+x[1]<ans)
                {
                    q.push({x[0],currCost+x[1],currK+1});
                }
            }
            
        }
        if(ans == INT_MAX)
        {
            return -1;
        }
        return ans;
    }
};

我使用了BFS算法。

但是,我得到了以下错误:

第924行:Char 9:运行时错误:引用绑定到类型为“std::vector,std::allocator”的空指针; >; >‘ (stl_vector.h)摘要:未定义行为消毒器:未定义-behavior/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../include/C++/8/bits/stl_vector.h:933:9

我无法找出我哪里出错了。

谢了。


共2个答案

匿名用户

vector<vector<vector<int>>>g; should be `vector<vector<vector<int>>>g(n);` 

其中n可以是任意数。 因为你试图获得特定的索引。 你必须初始化你的矢量。

匿名用户

请查看以下代码:

        vector<vector<vector<int>>>g;
        for(auto f:flights)
        {
            int from=f[0];
            int to=f[1];
            int cost=f[2];
            g[from].push_back({to,cost});
        }

最初g是一个空向量。 使用它所做的第一件事是访问不存在的元素:g[from]

其他注意事项:在不需要的地方使用向量。 使用已知固定数量的元素而不检查实际大小的事实意味着向量被误用:

            int from=f[0];
            int to=f[1];
            int cost=f[2];

通过使用结构,元组等来避免这种情况。