我正在做这个问题http://www.spoj.com/problems/SHOP/问题归结为计算加权图中的两点之间的最短路径，其中顶点具有权重。我使用 bfs https://code.hackerearth.com/ff00c2Z 实现了一个工作解决方案，它在示例测试用例上运行良好，但当我用谷歌搜索一些解决方案时给出了 WA 判决 我看到实际的解决方案使用 dijkstra 。当我试图找出我的错误时，我发现我使用了 deque 而不是优先级队列，在这种情况下它有什么区别？为什么 deque 不起作用？我的方法错了吗？那么这个问题怎么用BFS来解决呢？
最佳答案
您正在使用deque而不是优先级队列，并且您想知道出了什么问题？
首先，在出队中，您没有根据距离对此处的事物进行优先级排序。第一个入队对象或最后一个入队对象始终被赋予最高优先级，但可能会出现中间元素应具有最高优先级的情况(它可能成为最高优先级对象)，这就是您获得 WA 的原因。
注意:我刚才已经说了使用dijkstra的前提条件。您还可以使用 BFS 以及 Dijkstra 来解决此问题。
注2:在需要时使用数据结构。在 BFS 中不需要双端队列，只需使用队列就足够了，否则处理大型代码会变得更加复杂。
关于algorithm - 优先级队列和双端队列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33244353/