以前见过一篇另类堆优化dij的题解，然而找不到了
那位作者称它为dij-spfa（大概是这个意思，然而确实很形象
这方法比较玄学，正确性没有严格证出来，然而对拍是验证猜想的最好途径
不过也可能并不玄学，只是我一时没想出来而已，如果有见解可以发在评论
还有一个关于这个的讨论帖
众所周知，dij堆优的代码是这样，用了STL：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct node{
int w;
LL v;
bool operator < (const node& x) const{
return v>x.v;
}
};
int n,m,s;
LL dis[100006],vis[100006];
int fir[100006],nex[200006],to[200006],v[200006];
priority_queue<node>q;
void dij(){
memset(dis,0x3f,sizeof dis);
dis[s]=0;
q.push((node){s,0});
while(q.size()){
int u=q.top().w;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=fir[u];i;i=nex[i]){
int vv=to[i];
if(dis[vv]>dis[u]+v[i]){
dis[vv]=dis[u]+v[i];
q.push((node){vv,dis[vv]});
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
to[i]=y;v[i]=z;
nex[i]=fir[x];
fir[x]=i;
}
dij();
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
}
思考一下这个重载运算符：
struct node{
int w;
LL v;
bool operator < (const node& x) const{
return v>x.v;
}
};
和这个入队操作：
if(dis[vv]>dis[u]+v[i]){
dis[vv]=dis[u]+v[i];
q.push((node){vv,dis[vv]});
}
每次入队，都是把节点编号和当前节点距离做成结构体
然而，在这个结构体在优先队列的期间，这个(dis)的值可能会变（被松弛了），然而这并不影响结构体里的值
那么，我们可不可以只让节点号入队，然后比较节点的(dis)
然后，再结合一点spfa，给每个点记录是否在队中，如果在，就只松弛不入队
那么稍加改动可以写出这样的代码，当然这里我优先队列是手写堆实现的，(vis)记录的是是否在对中：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
#include<iomanip>
#include<cstring>
#define R register
#define LL long long
inline int read(){
int x=0,y=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') y=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+(c^48);
c=getchar();
}
return x*y;
}
int n,m,s;
int to[200006],net[200006],v[200006];
int tot;
int fir[100006],dis[100006];
bool vis[100006];
int dui[100006],sz;
void swapn(int &ii,int &jj){
ii^=jj;
jj^=ii;
ii^=jj;
}
int minnpop(){
int res=dui[1];
dui[1]=dui[sz];
dui[sz]=0;
sz--;
int i=1,L,r;
while(i*2<=sz){
L=i*2;
r=L+1;
if(r<=sz&&dis[dui[r]]<dis[dui[L]]) L=r;
if(dis[dui[i]]<=dis[dui[L]]) break;
swapn(dui[i],dui[L]);
i=L;
}
return res;
}
void add(int x){
dui[++sz]=x;
int i=sz,p;
while(i>1){
p=i/2;
if(dis[dui[p]]<=dis[dui[i]]) break;
swapn(dui[p],dui[i]);
i=p;
}
}
void dijkstra(){
memset(dis,66,sizeof(dis));
dis[s]=0;
add(s);
vis[s]=true;
int st,now;
while(sz){
st=minnpop();
vis[st]=false;
for(R int i=fir[st];i;i=net[i]){
now=to[i];
if(dis[now]>dis[st]+v[i]){
dis[now]=dis[st]+v[i];
if(!vis[now]){
add(now);
vis[now]=true;
}
}
}
}
}
int main(){
n=read();
m=read();
s=read();
int sta,e;
for(R int i=1;i<=m;i++){
sta=read();
e=read();
v[++tot]=read();
to[tot]=e;
net[tot]=fir[sta];
fir[sta]=tot;
}
dijkstra();
for(R int i=1;i<=n;i++) printf("%d ",dis[i]);
return 0;
}
这种方法看似很乱搞，其实是能过的
为什么说他乱搞？因为可以看出：
if(dis[dui[p]]<=dis[dui[i]]) break;
这是堆操作的代码，我们(dui)数组存的是节点编号，比较规则是比较当期节点的(dis)
然而，每经过一次松弛，(dis)都会变，但此时我们并不会刻意去调整堆结构
所以堆就乱了
那么它为啥还能过？个人认为是：在频繁的push和pop中，恰好将堆的性质调整好了
因为只有目前不在堆中的节点才能入堆，所以堆中元素最多(n)个，让堆操作的复杂度大大减小，可能也是因为元素少了，堆性质更容易维护才使这个算法没有挂掉
回想一下第一种，只要当前节点被松弛了，就接着扔到堆里，之后每个节点只能被用来松弛其它节点一次，已经被用过的话就直接扔掉
但这个是，只要堆里有节点，不管它有没有别用去松驰过，都继续用它松弛（spfa的影子）
可能，除了堆操作以外的正确性，就是用这一点来保证的
目前，用这种方法写最短路的题，还没有挂掉过
并且，经过了@Nickel_Angel大佬的几百次(n leq 1000,m leq 10^5)的对拍，也没挂，并且感谢她，当时发那个讨论帖的时候我还不会对拍
而且，它更快！
普通版，800ms+
优化后，200ms+
用时是之前的四分之一
主要节省时间的地方，应该就是刚才说的堆的复杂度降低
而且在洛谷标准版最短路这样卡spfa的数据下，dij-spfa能跑出这样的时间，说明这个算法在用时上也是比较稳定
然而我用这个方法去做bzoj的那个需要用斐波那契堆或配对堆优化的dij，还是不能过
若干月后更新
今天刚好学到费用流，写用 dij 跑的原始对偶算法的时候，用了上面的写法，然而求出的 dis 数组出现了问题
但它与普通最短路的区别也只在于边权按照 G.c[i]+h[u]-h[v] 来计算，也许问题就出在这里吧，搞不太懂
所以如果使用起来和普通最短路有区别的时候还是少用这种方法吧