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

Question

m个航班连接了n个城市。每个航班从城市 u 出发，到达 v 的价格为 w.

现在给定所有城市和航班，以及出发城市 src 和目的地 dst，您的任务是找到从 src 到 dst 最多停靠 k 站的最便宜价格。如果没有这条路由，则输出-1.

例如：

示例 1：

输入：

n = 3, 

edges = [[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 行：字符 9：运行时错误：引用绑定到 'std::vector<std::vector<int, std::allocator >, std::allocator<std::vector<int, std::allocator > > >' 类型的空指针 (stl_vector.h) 摘要：UndefinedBehaviorSanitizer：未定义行为/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_vector.h： 933:9

我找不到哪里出错了。

谢谢。

Answer 1

查看这段代码：

        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].

你的意思可能是：

vector<vector<vector<int>>>g(n);

在这里，您创建一个 3D 向量，第一个维度已正确初始化。

其他注意事项：在不需要的地方使用向量。您在不检查实际大小的情况下使用已知固定数量的元素这一事实意味着向量被滥用：

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

尽量避免使用结构、元组等。结构更合适，因为您甚至知道每个元素的作用：from、to、cost .

这段代码效率很低：

for(auto x:g[currCity])
    ...

只要g是一个3D向量，auto x就变成了每个2D元素的完整拷贝。试试看：for(const auto &x:g[currCity]).

Answer 2

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

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

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

Got runtime error while using BFS algorithm

c++

graph

breadth-first-search

data-structures