【求助】dijkstra+heap

Dijkstra+Heap有两种写法
根据算法流程得到的比较中规中矩的实现方法是 维护一个有n个元素的堆
每次松弛完了以后 调整对应的元素在堆里的位置
这需要额外维护编号为i的节点在堆中的位置(在通过swap调整堆的时候更新一下就好了
另外一种就比较简洁一点 允许同一个节点以不同的距离标号出现在堆中
具体来说 堆中的元素都是形如(x,dis)的数对 表示一个节点及其距离标号
不管一个节点在堆里出现了多少次 最先被弹出的一定是我们需要的那个dis最小的
具体的实现就自己琢磨一下吧..
如果借助STL的priority_queue可以写得很短

swap指的是"将堆中两个元素的位置对换"的操作
所有对堆的维护都是用swap来表达的对吧 所以就在swap的时候进行维护信息就好了
第二种的话 要点在于 堆里存储的不是一个数 而是一个数对(x,dis)
假设我们试图用d[u]+w(u,v)去更新d[v] 那么就把(v,d[u]+w(u,v))加入堆中
然后每次从堆里取出dis最大的数对就好了

我不会c++ 只会c 能用stl吗？
不能用的话只能自己写了
……

在当每次松弛之后，往堆里加入的点已经符合堆的性质，不需维护，此时再往堆里加入刚刚松弛的点时，也是符合堆的，所以也不需要维护。