优先队列和双端队列
Priority queue and deque
我正在做这道题 http://www.spoj.com/problems/SHOP/ .The question boils down to calculating shortest path between 2 points in a weighted graph where verticecs have weights.i implemented a working solution using bfs https://code.hackerearth.com/ff00c2Z，它在样本测试用例上运行良好，但给出了 WA 判决，当我用谷歌搜索一些解决方案时
我看到实际的解决方案使用 dijkstra 。当我试图找出我的错误时，我看到我使用了双端队列而不是优先队列，在这种情况下它有什么区别？为什么双端队列不起作用？我的方法错了吗？那么如何使用 BFS 来解决这个问题呢？
您使用的是 deque 而不是 priority queue 并且您在问有什么问题吗？
首先，在 dequeue 中，您没有根据距离对事物进行优先排序。第一个入队对象或最后一个入队对象始终具有最高优先级，但中间元素可能具有最高优先级（它可能成为最高优先级对象），这就是您获得 WA 的原因。
注：我刚才说了使用dijkstra的前提条件。您还可以使用 BFS 和 Dijkstra.
解决此问题
注2：需要时使用数据结构。您不需要 BFS 中的双端队列，只需使用一个队列就足够了，否则处理大型代码会变得更加复杂。
我正在做这道题 http://www.spoj.com/problems/SHOP/ .The question boils down to calculating shortest path between 2 points in a weighted graph where verticecs have weights.i implemented a working solution using bfs https://code.hackerearth.com/ff00c2Z，它在样本测试用例上运行良好，但给出了 WA 判决，当我用谷歌搜索一些解决方案时 我看到实际的解决方案使用 dijkstra 。当我试图找出我的错误时，我看到我使用了双端队列而不是优先队列，在这种情况下它有什么区别？为什么双端队列不起作用？我的方法错了吗？那么如何使用 BFS 来解决这个问题呢？
您使用的是 deque 而不是 priority queue 并且您在问有什么问题吗？
首先，在 dequeue 中，您没有根据距离对事物进行优先排序。第一个入队对象或最后一个入队对象始终具有最高优先级，但中间元素可能具有最高优先级（它可能成为最高优先级对象），这就是您获得 WA 的原因。
注：我刚才说了使用dijkstra的前提条件。您还可以使用 BFS 和 Dijkstra.
注2：需要时使用数据结构。您不需要 BFS 中的双端队列，只需使用一个队列就足够了，否则处理大型代码会变得更加复杂。