我下午在做最短路时想到了 SPFA 可以使用堆优化来做，并且经过实践我得出了它确实有效。

正常的 SPFA ：记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

堆优化后的SPFA：记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

我的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,d,h[500005],ans[100005],js;
struct edge{
	int n,v,w;
}a[500005];
struct node{
	int id,w;
	bool operator<(const node &a)const{
		return w>a.w;
	}
};
void add(int u,int v,int w){
	a[++js].n=h[u];
	a[js].v=v;
	a[js].w=w;
	h[u]=js;
}
void spfa(int d){
	priority_queue<node> q;
	memset(ans,0x3f3f3f3f3f,sizeof ans);
	ans[d]=0;
	q.push(node{d,0});
	while(q.empty()==0){
		node f=q.top();
		q.pop();
		if(f.w>ans[f.id]) continue;
		int d=f.id;
		for(int i=h[d];i;i=a[i].n){
			int v=a[i].v;
			if(ans[v]>ans[d]+a[i].w){
				ans[v]=ans[d]+a[i].w;
				q.push(node{v,ans[d]+a[i].w});
			}
		}
	}
}
main(){
	cin>>n>>m>>d;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	spfa(d);
	for(int i=1;i<=n;i++){
		if(d==i) cout<<0<<" ";
		else if(ans[i]>=0x3f3f3f3f3f) cout<<"2147483647 ";
		else cout<<ans[i]<<" ";
	}
	return 0;
} 

之后我上网搜索，网络上很少有过关于 SPFA 堆优化的论述，就算有也讲的不太清楚，相信洛谷有人可以解答以下的问题：

1. 它的运行时间是否在遇到大部分数据时都小于等于普通的 SPFA ？

2. 它和 Dijkstra 一样吗？

3. 它能否继承普通 SPFA 的特点，如判断负环和处理负权图？