Dijkstra堆优化的写法讨论

## 本题解较适合堆优化重载括号运算符的同学看 众所周知， $Dijkstra$ 是一个常用来求没有负环的最短路的方法 一种常见的优化，就是优先队列（堆）优化 $Dijkstra$ 优先队列的写法对每个人来说也是各不相同 针对一种重载括号运算符的写法，我想谈一谈我的看法 代码： ```cpp struct cmp{ bool operator()(const int &x,const int &y) const { return dis[x]>dis[y]; } }; priority_queue<int,vector<int>,cmp>q; void dijkstra(){ int u,v,w; for(int i=1;i<=n;++i) d[i]=2147483647; dis[s]=0;q.push(s); while(!q.empty()){ u=q.top(); q.pop(); if(vis[u]) continue; vis[u]=true; for(int i=head[u];i;i=p[i].nxt){ v=p[i].to;w=p[i].w; if(dis[u]+w<dis[v]) { dis[v]=dis[u]+w; q.push(v); } } } } ``` 这种写法保留了 $priority\_queue$ 中小根堆原来的写法，更容易理解 并且这种写法在某本著名的书中也出现了 但是这种方法真的没有问题吗？ 我们可以考虑，如果在更新其他节点的时候，某一个节点被多次更新，那么它每次的 $dis$ 值都是会减小的 那么如果一个节点更新的次数足够多时，它总有一次会跟自己进行比较，那么它会因为自己与自己的 $dis$ 值相等而留在这个位置 那么它就会在堆中形成一种类似于“路障”的东西将堆的某些部分“堵住” 而这种写法在数据结构上也破坏了堆原有的性质，就会使算法出现错误 如下图： $q.push$ 表示松弛时的入堆操作， $1(10)$ 表示将节点编号为 $1$ 的 $dis$ 值修改为 $10$ $cmp\quad$ 是重载括号运算符的写法 $node\quad$ 是将节点编号和 $dis$ 值合并之后的写法（下面有代码） 注： $pair$ 写法与 $node$ 写法大致类似，在此不再阐述  很明显，当编号为 $2$ 的节点多次入堆之后，堆内元素已经产生了问题 所以，如果一张图中有大量的重边，就很容易会导致这样的问题发生 附上 $node$ 写法代码 ```cpp struct node { int u,d; bool operator<(const node& rhs) const { return d>rhs.d; } }; void Dijkstra() { priority_queue<node> q; for(int i=1;i<=n;++i) d[i]=2147483647; q.push((node){s,d[s]}); d[s]=0; while(!q.empty()) { node x=q.top(); int u=x.u; q.pop(); if(vis[u]) continue; vis[u]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v,w=e[i].w; if(d[u]+w<d[v]) { d[v]=d[u]+w; q.push((node){v,d[v]}); } } } } ``` 如果有什么更好（玄学）的重载括号运算符的写法可以私信我qwq